エンドポイントが円上にある線分の交差数を数えますか？

Question

---

入力は、円周上に位置する点は をペアリングして接続されている方法と言って線分を定義する2n個の整数の配列です。 （各点は、それに接続し、独自の対を有する。）

アレイ[2,3,0,1]読み取り：

ポイント0は2
ポイント1点に接続されている点に接続されている3
ポイント2は0
を指すように接続されています。ポイント3は ポイント1に接続されます

意味私たちは線分（0,2）と（1,3）を持っています。

点は、配列内にある と同じ順序で円に配置されています。 （正確な座標は無関係です）

ここに私の配列の例があります。 （1つの交差点が発生しました。）

出力は交差点の数です。 （2つの線分が接触する点の数）

これを計算するにはどのような方法が最善でしょうか？

public static int countIntersections(int[] world) { 
    int intersections = 0; 

    for (int i = 1; i < world.length; i++) { 
     for (int j = 0; j < i; j++) { 
      if (!C(i,world[i],i-j,world[i-j])) { 
       intersections++; 
      } 
     } 
    } 

    return intersections; 
} 

public static boolean C(int a, int b, int x, int y) { 
    return ((a <= x && b <= x) || (a >= x && b <= y) || (a >= x && b >= x)); 
} 

彼らに仕事の両方を意味する私の最初のコードと同じ結果を与える：sabyの答えに

public static int count(int[] world) { 
    int i = 0; 
    int intersections = 0; 
    int endpoint = 0; 

    // run trought all points in order, find their pairs and check if the line they make is intersected 
    while (i < world.length - 1) { 

     if (world[i] == i+1) { // if 2 neighbouring points are connected, there are no intersections with the line they make 
      i++; 
     } else if (world[i] > i) { // don't need to check previously checked pairs 
      endpoint = world[i]; 

       // check if any intersections with the line L(i,world[i]): 
       // This goes through all points that are located before the endpoint of the line defined by point i and its pair world[i] 
       // And checks if their pair is located after the endpoint, which means that the line they make intersects the line L(i,world[i]) 
       for (int j = i+1; j < endpoint; j++) { 
        if (world[j] > endpoint) { 
         intersections++; 
        } 
      } 
     } 
     i++; 
    } 

    return intersections; 
} 

おかげで、私はまた、これをコード化：私が試した何

！しかし私の初期のコードはこれより高速です。

両方のコードが動作し、最適化の質問がCodereviewに適しているので、私は彼の答えを受け入れます。

---

Answer 1

観察：2つのセグメントL1: [a, b]とL2: [x, y]を考えると、彼らDONTは場合にのみ(a < x && b > y) || (x < a && y > b)場合交わります。 これをC(L1, l2)と呼んでください。アルゴリズムの

概要：一対一

による線分上

• 反復は、最初の線分L1
• テイクセグメント線分L2を取り、条件C(L1, L2)計算します。 falseの場合、交差点の数に1を加えます。
• セグメントL3をとり、C(L3, L1)とC(L3, L2)と計算します。それに応じて1を追加します。O(n^2)：セグメントのLnについては
• は、あなたがC(Ln, Ln-1)、C(Ln, Ln-2) ...
• 時間計算を計算する必要があります。 nはセグメント数です