輪ゴムをはるというプログラムの問題が難しくて

[堀江伸一]

http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 68&lang=jp

この問題なのですが難しくて解けずに困っております。
勉強なのでできるだけ自力で解きたい。
でも、難しいので自信が持てない。

といった状態です。

一応自分としては、輪ゴムで囲むということを言いかえると、ある2点間を結ぶ線分を順に引く作業と言いかえることができる。
2点間を結んでいい条件は、2点間を結ぶ直線で平面を２つの半開平面に分けた時、残りの点が全てどちらかの平面にあればその2点に線分をひいて良い。

とか考えたのですが、数学的に大丈夫か自信が持ててない状態です。
どなたかアドバイスお願いします。

[たいちう]

グラハム走査について調べてみましょう。

[たいちう]

できるだけ自力でやりたいのでしたね。

一応自分としては、輪ゴムで囲むということを言いかえると、ある2点間を結ぶ線分を順に引く作業と言いかえることができる。
2点間を結んでいい条件は、2点間を結ぶ直線で平面を２つの半開平面に分けた時、残りの点が全てどちらかの平面にあればその2点に線分をひいて良い。

このアルゴリズムでも可能です。勉強のためには、自分で考えたアルゴリズムで完成させてから、グラハム走査のプログラムを作成することをお勧めします。

[堀江伸一]

ありがとうございます。
グラハム走査。
計算量が小さい方法ですね。
私の素朴な方法だと計算量が多くなると。

どんな問題にも賢い方法というのはあるのですね。
うーん自分で考えた方法で解いて満足するだけじゃなくきちんと調べるのも大事。
なのかも。

勉強になります。