TobiasGSmollett https://blog.hatena.ne.jp/TobiasGSmollett/ tobiasの日記 https://tobiasgsmollett.hatenadiary.org/ AOJ 幾何 データ構造 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A 書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で紹介されいるが、セグ木を使って効率よく解けると書いてあったので実装。 x座標を座標圧縮すると平面走査で使っている二分探索木の部分にセグ木を使えてO(n log n)になる……ということだと思う。 #include<iostream> #include<vector> #include<algorithm> #include<map> #define all(c) (c).begin(),(… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftobiasgsmollett.hatenadiary.org%2Fentry%2F20150217%2F1424160997" title="CGL_6/A: 線分交差 - tobiasの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-02-17 17:16:37 rich https://tobiasgsmollett.hatenadiary.org/entry/20150217/1424160997 1.0 100%