C. Ancient Berland Circus
この手のコンテストには恐れをなして、取り組もうとしてこなかったのだが、出来ることを期待せず気まぐれにやろうとして挫折。
- 標準入力から取り込むコードは後で書く。list1にテストデータを放り込む。
- ざっくりと、なのでコードの長さとか汚さとかメモリ使用量とか気にしない。っていうか気にする余裕がない。
- 処理時間は気にしない。
- System.Drawing.PointFを使おうとしたが、誤差が出るのでPointDなる構造体を実装。
- とりあえず、与えられた3点(点A,点B,点Cとする)を頂点とする三角形の外心円の中心Nを求めようとした。
- Nは弦の垂直二等分線の交点である、ということを利用することを企む。
- 二本の直線の式から求める式を紙で書いたら異常に複雑だったことに加え、垂直な直線で傾きが出せずに場合分けが複雑になるのが嫌だったので、点Aと原点Oが一致するようにB,C,Nを平行移動させ、これを点D,点E,点Fとしたのち、ODがx軸と重なるよう、Oを中心としてD,E,Fを回転させて、G,H,Iとする。そのため、DとEの座標、x軸がOD,OEとなす角をMath.Atan2(double,double)を利用して求めて計算。
- OFの垂直二等分線は簡単に求まるからHのx座標が求まり、OIの垂直二等分線の式もそれほど難しくない。x座標がもとまっているんだから代入するだけでHのy座標も求まる
- OGがODに一致するようにIを回転させてJとし、点Oが点Aに一致するようにJを平行移動すればNと一致する。
- ∠ANB,∠BNC,∠CNAの最大公約数を求め、2 * Math.PIをその公約数で割れば多角形の最小角数がわかるかな、と。多分基本的に角数が多いほうが面積広いと思うので。で、この多角形の角数が分かれば後は面積を求めるだけ…
そう思って書いては見たものの、最大公約数120°が表示されないために悩み、
Double.Epsilonと比較するよう修正し、3を求めることが出来たようだ。修正版1(追記参照)
先程、3が出なくて悩んでいたのだが、多分弧度法であるということを何か誤解して360を分子にでもしてしまっていたのだろう。
TODO:大雑把に方針は決しているが、与えられたサンプルを入力しても多分4が出ないので、お粗末にしていた部分を作る…と思ったらサンプルの入力に限りここは不要かな?修正版1で修正済み
別な問題が発生した。2 * Math.PI を超えたり、0を下回ったりするときの対処が抜けているようだ。修正版1で修正済み
- TODO:標準入力と標準出力
- TODO:速度と桁数の測定
追記1:Epsilonとの比較の向きが違うような気がしたけど、直したら期待する答えにならないのでちょっと考えてる。
追記2:向きが違うのは正解。問題はMath.Floorにあった。とりあえず暫定的な修正を加えた(既に反映済み)が、凄くいきあたりばったりで、個の数字で問題ないかは正直言って自信がない
修正版は一応、角数を求めることを前提としている。