主食は米

主に競プロ備忘録

AGC 021 B - Holes

解法

前提知識: 凸包 (ググればいっぱい出てくる)
Rが十分に大きいので数学的にINFだとして考察していく.
各点に落ちるような領域は与えられた二点の全ての組を取った垂直二等分線で区切られる(ボロノイ図と言うらしい)
R=INFなので,この領域が有限領域であればそこに落ちる確率は0となり,そのような点は凸包に含まれない点である.
よって凸包同士の垂直二等分線で区切られた領域を考えていく.
上の考察から有限領域は無視して良いので,凸包内部の領域は無視して図でのa/2PIがAの全体に対する比率となると考えても良い.
f:id:kurarrr:20180227002710p:plain
青aの角度は外角の赤aと等しいので,凸包で隣接する点との外角を求めそれを2PIで割る.

凸包の出力は反時計回り順に出てくるので素直に実装している.
ただし,-PI < arg(Point) < PIとなるので一方が境界(PI)を超えて負になった場合には+2PIして補正しないといけない.

またindexと点をmapで紐づけているが,その場合比較関数compが必要となる.

メモ

凸包の問題解いたことなかったけど割と素直に思いついたので出たかったね.
ライブラリはasi1024さんの使わせて頂いています.

コード