問題 Editorial 問題 整数座標x,yで単純多角形が与えられる。整数denomが与えられる。 全ての整数a,bに対して座標(denom*a,denom*b)を考える。この座標のうち与えられる多角形に含まれる座標すべてにwifiを置きたい(wifi点と呼ぼう)。wifi点はいくつあるか求…

問題 Editorial 問題 凸多角形(x,y)が与えられる。 ある整数点がN-coolであるとは、多角形の中(辺上も含む)にあって、少なくとも1つのN-coolな線分の端点となっていることである。 ある線分がN-coolであるとは、多角形の中にある整数点を少なくともN個含むこ…

問題 Editorial 問題 2つの凸多角形の共通部分の面積を求めよ 解答 ライブラリゲー Spaghetti Sourceさんhttp://www.prefield.com/algorithm/index.html のコードを使った コードはほぼSpaghetti Sourceさんのコードそのままなので、ここに貼るまでも無いの…

問題 Editorial 問題 初期状態として、整数座標上の点がいくつか与えられる(xs, ys)。 いつでも、任意の点2つ(p, q)に対して((p.x + q.x) / 2.0, (q.x + q.y) / 2.0)の点を作ることができる。 この操作を無限にどんなふうにでも繰り返せるとき、全ての点を被…

問題 Editorial 問題 直径dの円周上のcつの点を与えられる。 この点のどれか4つを選んで四角形を作るとき、面積を最大化せよ 1 4 解答 四角形は2つの三角形に分けられる。 対角線上の頂点を2つ全探索したら、その左右で3,4つ目の点を独立に選べる。 3,4つ目…

問題 Editorial 問題 (凸とは限らない)単純多角形の三角形分割を、辞書順最小でしろ。 引かれた対角線と多角形は、始点・終点以外で交差や触れてはならない 解答 まず、適当に対角線をひいても、三角形分割ができなくなることはない。つまり単純な辞書順gree…

問題 Editorial 問題 HexMapがあって、座標が2つ与えられる。 その点と点を結ぶ線分と交差する6角形の数を答えよ。 ただしエッジの上にオーバーラップする場合や、角の1点だけで触れる場合はカウントしない 10000 解答 Editorialを読んだ。 まず、座標を斜め…

問題 Editorial 問題 長方形Aが一つ与えられる。 別の長方形Bが与えられ、それを幾つか置いて先の長方形Aを被覆したい。 ただし、置くのに、与えられた角度だけ回転させて置かなければならない。 置く長方形の数を最小化せよ。 -100 0 角度が0と90以外なら、…