2020年6月15日月曜日

CodeChef June Challenge 2020 - The Delicious Cake

CodeChef June Challenge 2020 - The Delicious Cake

与えられた点集合の凸包を考えるとき、凸包上の点をいくつか省いて内側の多角形に使うことは不可能に見える。そこで、凸包を何回も取ってネストされたレイヤー(凸多角形)を作り、クエリで与えられた頂点がどのレイヤーに含まれるか調べるというのを基本方針として思いつく。

ただ、与えられた点で1つのレイヤーの内部に含まれるものはそれ自身がいずれかのレイヤーに属さなければならないという条件がちょっと厄介に見える。縮退が起きている場合の扱いも書かれていなくてよくわからない。

しかし、とりあえず面倒なことは一切起こらないものとして、単純なコードを提出してみたら通ってしまった。(EPSすらちゃんと考慮していない)