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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
堀江伸一

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

#1

投稿記事 by 堀江伸一 » 14年前

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

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

といった状態です。

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

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

たいちう
記事: 418
登録日時: 14年前

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

#2

投稿記事 by たいちう » 14年前

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

たいちう
記事: 418
登録日時: 14年前

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

#3

投稿記事 by たいちう » 14年前

できるだけ自力でやりたいのでしたね。
一応自分としては、輪ゴムで囲むということを言いかえると、ある2点間を結ぶ線分を順に引く作業と言いかえることができる。
2点間を結んでいい条件は、2点間を結ぶ直線で平面を2つの半開平面に分けた時、残りの点が全てどちらかの平面にあればその2点に線分をひいて良い。
このアルゴリズムでも可能です。勉強のためには、自分で考えたアルゴリズムで完成させてから、グラハム走査のプログラムを作成することをお勧めします。

堀江伸一

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

#4

投稿記事 by 堀江伸一 » 14年前

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

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

勉強になります。

閉鎖

“C言語何でも質問掲示板” へ戻る