人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

ご相談です。というか頭の体操かもしれません。

・机の上にを5個のおはじきを無造作におきます。

このとき、おはじき同士を結んでできる図形のうちで、一番面積の大きい図形を見つけるアルゴリズムを考えよ。

また、その図形の面積を求めるアルゴリズムを求めよ。

おはじきの座標(X,Y)は分かっているものとする。


一番シンプルで美しい回答がでる事を楽しみしております。

もしかすると常識問題なのかもしれませんが、、
どうぞ宜しくお願い致します。

1404392810
●拡大する

●質問者: ふぃふぃ
●カテゴリ:インターネット 科学・統計資料
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● Sampo
ベストアンサー

一番大きい図形は凸多角形なので、面積を求めるのは簡単です。
凸多角形ABCDEの面積は△ABC+△ACD+△ADEと機械的に分割できますから各三角形をヘロンの公式で求積するだけです。

さて凸包を求めるアルゴリズムを、lang_and_engineさんご紹介のとは別のアプローチで。

こういうイメージでいきましょう。ピンが5本打たれた板に、水平にした定規を上から下ろしてきて、ピンにぶつかったらそこから時計回しに回していきます。ぶつかったことのあるピンに再びぶつかったら計算終了。

最初のピンは、Y座標が最大となるピンですね。ではそれ以降。
平面ベクトルで考えます。記法ですが、ベクトルXを長さで割って単位ベクトルにしたものを[X]と書くことにしましょう。

  1. 定規は初期で水平なので、定規ベクトルRは(1,0)
  2. 最初のピン(Aと名付けます)から各ピンへのベクトル AB, AC, AD, AEはすべて定規ベクトルの左側にはありません。
  3. なので、定規ベクトルの右側直近のものは、Rとなす角θが最小、言い換えればcosθが最大のものです。内積 R・[AB], R・[AC], R・[AD], R・[AE] を調べて最大のものが「次のピン」です。次のピンがBだったとしたら、定規ベクトルRは [AB]になります。
  4. すでに出会った点が出てくるまで3に戻って続けます。

ふぃふぃさんのコメント
とても分かりやすい説明をしていただきありがとうございます。 内積でポコポコ探していく様子が頭に浮かびました。 これなら僕でも実装できそうだと感じました。 参考にさせていただきます。 どうもありがとうございました。

Sampoさんのコメント
高校の数学がものすごく実用的なことを教えてくれていることに気づいてもらえたらうれしいです。 図形絡みのプログラミングで迷ったときはベクトルと一言唱えると大抵なんとかなります。
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ