drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ HUPC 計算幾何 平面グラフ 多角形 偏角ソート グラフ DFS サイクル 二次元平面上のN点の問題 けんちょん自作問題 サイクル検出 原案でした！僕は比較的アドホック寄りの問題を作る傾向があったかもだけど、これは典型な感じ。 問題へのリンク 問題概要 頂点数 、辺数 の連結な平面グラフが与えられます。ここで、各頂点の座標 も入力として与えられます。 どの 3 点も一直線上にはありません。また、橋も関節点もありません。したがって、平面グラフは多角形を敷き詰めたものとみなすことができます。これらの多角形のうち、内部に頂点や辺を含まないものの面積の最大値を 2 倍した値を求めてください。 制約 考えたこと 多角形をすべて抽出しよう！！！ 各頂点 v ごとに、あらかじめ、v に接続する辺を偏角でソートしておくことにする。 そして、平… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F09%2F16%2F200200" title="AOJ 3176 Plane Graph (HUPC 2020 day3-E) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20200916/20200916195857.png Hatena Blog https://hatena.blog 2020-09-16 20:02:00 rich https://drken1215.hatenablog.com/entry/2020/09/16/200200 1.0 100%