2017-03-25 13 views
0

入力は、円周上に位置する点は をペアリングして接続されている方法と言って線分を定義する2n個の整数の配列です。 (各点は、それに接続し、独自の対を有する。)エンドポイントが円上にある線分の交差数を数えますか?

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

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

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

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

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

enter image description here

出力は交差点の数です。 (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に適しているので、私は彼の答えを受け入れます。


答えて

0

観察: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はセグメント数です
  • +0

    なぜdownvoteですか? – saby

    +0

    +1、後で試してみます。私は誰かが通り過ぎていて、質問とこの答えの両方を理由なしでdownvotedしたと思います... – Vepir

    +0

    どのくらい奇妙です!はい、試して、フィードバックをしてください。あなたが時間の複雑さを改善したいなら、それができるかもしれません。 – saby

    関連する問題