betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 C - 2D Plane 2N Points 以前の自分が解法の正当性を理解するのにすごく悩んだ問題で、印象深いです。 解法 考察 2次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば 座標でソートして小さい順番に見ていき、もう一方の 座標についてはデータ構造などを用いて処理していくテクニックです。軸に平行な直線をスライドさせて平面全体を走査していくので、Codeforcesなどの英語解説では「scanline algorithm」と書かれたりします。 また赤と青、左端と右端など2種類の要素をペアにする問題では、平面走査や数… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F09%2F07%2F224528" title="AtCoder Regular Contest 092 C - 2D Plane 2N Points - ARMERIA" 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.user.blog.st-hatena.com/default_entry_og_image/106916089/1592411661884548 Hatena Blog https://hatena.blog 2020-09-07 22:45:28 rich https://betrue12.hateblo.jp/entry/2020/09/07/224528 1.0 100%