-1

トピックが混乱している場合は申し訳ありません。何を探しているのかわからないからです。ポイントのセットPがあります（|P| < 10^5）。各ポイントには整数座標があります（between -10^4, 10^4）入力で指定されたすべてのポイントにまたがる直線を見つける方法。条件は、線が最も太くなければならず、その直線の太さを小数点以下2桁までの精度で出力する必要があります。ヒント、手がかり、アイデア、またはアルゴリズム名をいただければ幸いです。

PS。宿題でもSPOJでもありません。前回の問題をやってプログラミングコンテストの準備をしているところです。そして、それは私が解決できないものであり、解決策を探すためにどこから始めればよいのかわかりません...

4

2 に答える 2

1

この点群の凸包を決定することから始めて (例: http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htmを参照)、このポリゴンを最短距離で結ぶ 2 本の平行線を見つけようとします。

平行線の方向を凸包のセグメント (数には限りがあります) に基づいて設定できるため、これはより簡単な問題であると思います。

1 つの実装は、凸包の各セグメントを順番に処理することです。セグメントごとに、それを通る線を引き (これは 2 つの平行線の 1 つです)、凸包を囲む最も近い他の平行線を決定します。これまでに見つけた平行線間の最小距離を記録しながら、凸包の各セグメントに対してこれを行います。最後に、最適な結果が得られるはずです。

明らかに、これには、最も近い他の平行線を決定するための効率的な方法が必要です。これを行う (素朴ですが、おそらく十分な) 方法は、現在のセグメント上にない凸包のすべての頂点を取得し、それを通る線までの垂直距離を決定することです (例: http://en.wikipedia .org/wiki/Distance_from_a_point_to_a_line )。これらすべての頂点の最大距離は、平行線までの最小距離でもあります。

擬似コード:

Function FindThinnestLine(PointCloud P)
   CH = ConvexHull(P)

   optS = nothing
   optDist = infinite

   For each segment S in CH
      L = the line through S

      /* Find the minimum distance that the line parallel to L must have in order to enclose CH */
      maxDist = 0
      For each vertex P in CH, except the two that limit S
         dist = The distance between L and P
         maxDist = max(dist, maxDist)

      /* If the current S has a smaller maxDist, it is our new optimum */
      if(maxDist < optDist)
         optS = S
         optDist = maxDist

   Return the line through optS and the line parallel to optS at a distance of optDist as the result
End Function

これは O(n^2) アルゴリズムで、n は凸包のセグメント数です。

編集 考えてみると、すべての S に対して (maxDist を見つけるために) 凸包の O(n) 頂点を反復処理する必要はありません。最初のS に対してのみです。この最初の頂点を oppV と呼ぶとしましょう。 ( S の反対を表す opp )、凸包のセグメントを時計回りに処理するとします。後続の S を処理するたびに、新しい oppV は同じ頂点またはその右隣の 1 つになります (ただし、左隣ではありません。そうでない場合、セグメントは凸多角形を形成しません)。
したがって、凸包のセグメントの処理は O(n) で実行できます (ただし、凸包の作成は依然として O(n log n) です)。

于 2012-11-16T10:06:44.890 に答える
0

P の特定のサブセットのすべてのポイントを含む最も太い線は、セグメント の垂直二等分線である必要がありますxy。ここで、xとyはサブセットの 2 つのポイントのhighest distance d間にあります。この線の太さdも同様です。

于 2012-11-16T10:03:27.663 に答える