日々の流転

λ. ICPC過去問: Circle and Points

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

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

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

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