解法 :双対グラフを作ってbfs すれば良い... が, グラフ構築バグりまくってます. 悲しい. (まだWA...) 朝にバグ取ります...コード : int main() { int N, M; while (scanf("%d %d", &N, &M) && N){ vector<Point> P(N); vector<int> to[128]; bool exist[128][128] = {0}</int></point>…

問題文 : Polygon-Point Containment

問題文 : Pie Chart is as easy as pie.

問題文 :平面上に与えられた$N$ 個の点から, ちょうど$k$ 個の点を結んでできる凸多角形のうち、最も面積の小さいものを見つけるプログラムを作成せよ. ただし, $N$ 個の点の座標を与えられた後, 質問として凸多角形の角の個数$k$ がいくつか与えられる.$N \…

問題文 : Stoning Fortune解法 : 線分の交差判定・交点判定がきちんとできていれば, 面積を求めて条件に合わせて出力を行う問題. ライブラリを頼りました.

問題文 : 最後の扉解法 : つながる三角形を列挙したら, 強連結成分分解を行うだけ. JOI のAdvertisement という問題と全く一緒になります. 問題のつながる三角形の列挙ですが, 長方形と辺が重なる or 三角形の頂点が長方形にはいる or 長方形の頂点が三角形…

問題文 : 最古の遺跡2解法 :dp[i][j] : 辺ij を最後に使った時の頂点数の最大値, とする. このとき, 以下のような図を考える.ここで, 現在赤の辺から水色の辺に遷移しようと考えていたとすると, 赤の辺と水色の辺のなす角θが180 度以下であれば, dp[水色の辺…

問題文 : 直線解法 :オイラーの多面体定理です."V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"が成立するので, D=2から, F = E + 1 - V が求まります. EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出…

問題文 : 夜警解法 :登場する点のうち,・警備員のいる点 ・建物の点を頂点としたグラフを作る. この際に, 建物の辺または対角線と交わっている時は辺を貼らないようにする.これが出来れば, あとはダイクストラ法を各点に行うだけである.コード : #include <cstdio> #</cstdio>…

問題文 : 秋のイルミネーション解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.ここで, 四…