TTPC2015 H. 包囲 講評

問題

https://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_h

解説

https://bitbucket.org/ttpc2014/ttpc2015/overview

想定解法

幾何+全探索です.

$2$点を結んだ線分上に原点がないならば三角形を作ればよいです.
線分上に原点があるときは.その線分で残りの点群を上と下に分けて上と下で三角形を作ってくっつけた四角形を作ればよいです.$O(N^3)$でできます.

提出者の解法

幾何+全探索よりも偏角ソートしてDPが多かった印象です.全くもって想定外の解法でした.

よくあったミス

幾何+全探索の人は、線分と点の交差判定が間違っている人が多かったように見えます.同じ直線上に載っているかどうかを判定するだけではダメです.

よく引っかかったケース

原点を通るある直線上に全ての点があるケースや,原点を中心とする正方形のみからなるケース,原点の周りに原点を線分上に含む点が2点だけあり残りの点はランダムにバラまいたケースで落ちている人が多かったと思います.

感想

思った以上に解かれませんでした.答えが三角形か四角形になるという考察が思ったより難しかったのかもしれない.$100$点問題で幾何というのも敬遠された原因かな?ライブラリを持っていない人にはとても厳しい問題だったかも.

evimaさんの言うとおりWAが大量に出ていて手は出しづらかったかもしれない.想定解法までたどり着くとバグらせる要素が(ほぼ)ないので,人々がなんでこんなにWAを出すのか本当に分からず頭を抱えていました.

やっぱり考察が重かったかも?サンプルに四角形が答えになるケースは入れておいたが…

幾何問題は本当に全然解いたことがないのにこの問題を作ったので他の解法を作ったりができず結構不安だった.テストケースもどんなものを用意するかイマイチ分からなかったので思いつくケースをとにかく突っ込んでしまった.少ない数のテストケースでありうる嘘解法を撃墜するようなケースを網羅するのは本当に難しい.

想定解法までの考察パートはやや重め,実装は幾何にしては非常に軽い問題で,16問セットの中でもいい存在感のある問題だと個人的には思っています.