November Rain(1)

• どこから手をつけるか

この問題を見て最初に思い浮かんだのは、2008番でk.inabaさんの説明(http://d.hatena.ne.jp/Ozy/20060201#p1)を見て知った範囲の重なり部分を見つける方法。図のように各セグメントの端点ごとに領域を区切り、それぞれのエリアでセグメント同士の重なり具合を調べれば、一番上のセグメントもセグメント同士のつながりも見つけられるんではないか。
・・・となれば、すべての座標をごちゃまぜソートする必要があるので、セグメントの左右を表す情報と、元のオーダーに復元（あるいは高速アクセス）するためのインデックスが必要になる。というわけで、まずはこのような構造体を作ることにしよう。

struct POINTS
{
  int x,y;
  int index;
  int edge;
} p[80020];

80020としているのは、境界チェックが面倒なので保険ということでｗ
コイツをソートしてやる。ソートのルールは

①x座標が小さい順
②x座標が等しい時は左端の点を優先
③x座標が等しくしかも両方左端の点ならy座標の小さい方を優先
④①〜③に当てはまらない場合はy座標が大きいほうを優先

としておこう。

つづく