トップ «前の日記(2005-06-27) 最新 次の日記(2005-06-29)» 月表示 編集

日々の流転


2005-06-28 [長年日記]

λ. ICPC過去問: Circle and Points

例によってHaskellで瞬殺(Circle_and_Points.hs)。本番じゃHaskell使えないけどな。

あるn(≧2)点を囲むような円があるとする。このとき、円をずらすことで、それらの点を全て囲んで、かつその内の2点が円周上にくるようにすることが出来る。つまり、2点が円周上にくるような円だけを調べても一般性は失われない。(2005-07-22 追記: このことについては sheepman さんによる説明 が分りやすい)

(追記: 誤差が少し心配だったので、円周上に持ってきた二点を無条件で円に囲まれているものとして扱うよう変更した。)

それと、sumimさんがSmalltalk版を書いてくれました。Smalltalkの勉強になります。

本日のツッコミ(全3件) [ツッコミを入れる]
ψ ささだ (2005-06-29 15:02)

そいつの一般性が失われない理由がよくわからなくて。

ψ ささだ (2005-06-29 18:14)

やっとわかった気がするけど言葉に出来ないなぁ。

ψ さかい (2005-06-30 01:05)

そうなんですよ。<br>言葉でどう表現するのがいいのか僕も良くわからなくて……<br><br># 数学には何か便利な表現はないのかな。<br># 次回の圏論勉強会のときにでも豊福さんに訊いてみよっと。