6

私はたくさん検索しましたが、この場合に有効な答えが見つかりませんでした。水平または垂直の長方形がいくつかあります。ページ上にランダムに配置できます。それらは重なり合うか、共通のエッジを持つか、互いに分離することができます。これらの長方形の周囲と面積を見つけることができる O(nlogn) のアルゴリズムを見つけたいです。これらの写真は問題を明らかにするかもしれません。

ここに画像の説明を入力

インターバルツリーが役立つと思いますが、どうすればよいかわかりません。

4

2 に答える 2

8

これは、スイープラインアルゴリズムによって実行できます。

左から右に仮想線をスイープします。線と一連の長方形の交点が一連の間隔を表す方法と、長方形の左端または右端に遭遇すると変化することに気付くでしょう。

x 座標x1とx2の間で交点が変わらないとしましょう。次に、 x1の後の交点の長さがLである場合、 x1からx2までスイープすることにより、線は ( x2 - x1 ) * Lに等しい領域をスイープします。

たとえば、次の図では、x1を左の青い線、x1を右の青い線として見ることができます (これは私があなたから盗み、少し変更したものです :)): ここに画像の説明を入力

スイープラインの交点がこれらのポイント間で変化しないことは明らかです。ただし、青い交差点は赤い交差点とはかなり異なります。

これらの操作を含むデータ構造が必要です。

insert_interval(y1, y2); 
get_total_length();

これらはセグメント ツリーで簡単に実装できるので、ここでは詳しく説明しません。

さて、アルゴリズムは次のようになります。

  1. すべての垂直セグメントを取得し、x 座標で並べ替えます。
  2. 関連する x 座標ごとに (長方形のエッジとして表示されるもののみが重要です):
    • x1 を以前の関連する x 座標とします。
    • x2 を現在の関連する x 座標とします。
    • データ構造によって与えられる長さを L とします。
    • (x2 - x1) * L を総面積合計に追加します。
    • データ構造から x = x2 セグメントのすべての右端を削除します。
    • x = x2 セグメントのすべての左端をデータ構造に追加します。

左と右とは、長方形の辺を意味します。

このアイデアは、面積を計算するためだけに与えられたものですが、周囲を計算するように変更することができます。基本的に、交点が x 座標で変化する前と変化した後の交点の長さの差を知りたいと思うでしょう。

アルゴリズムの複雑さは O(N log N) です (入力として取得する値の範囲によって異なりますが、これは簡単に処理できます)。

TopCoderで、スイープラインアルゴリズムの広範なトピックに関する詳細情報を見つけることができます。

セグメント ツリーのさまざまな使用方法については、PEG ジャッジ wikiを参照してください。

これは、 SPOJ 問題 NKMARSの解決策としてのアルゴリズムの私の (本当に古い)実装です。

于 2013-01-24T17:13:36.543 に答える
0

以下は O(N2) 解です。

int area = 0;
FOR(triange=0->N)
{
    Area = area trianlges[triangle];
    FOR(int j = triangle+1 -> N)
    {
        area-= inter(triangle , j)
    }
}
return area;

int inter(tri a,tri b)
{
    if ( ( min(a.highY ,b.highY) > max(a.lowerY, b.lowerY) ) && ( min(a.highX ,b.highX) > max(a.lowerX, b.lowerX) ) )
    return ( min(a.highY ,b.highY) - max(a.lowerY, b.lowerY) ) * ( min(a.highX ,b.highX) - max(a.lowerX, b.lowerX) )

    else return 0;
}
于 2013-01-24T17:15:22.437 に答える