anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ SRM 幾何 座標変換 問題 Editorial 問題 HexMapがあって、座標が2つ与えられる。 その点と点を結ぶ線分と交差する6角形の数を答えよ。 ただしエッジの上にオーバーラップする場合や、角の1点だけで触れる場合はカウントしない 10000 解答 Editorialを読んだ。 まず、座標を斜めに変換する(Editorialの図を参照)。こうすることによって座標が整数で扱えるようになる。 この変換では2点を結ぶ線分の交差状況が保存されることに注意。 あとは適当に当たりそうな六角形を列挙し、エッジと交差判定をしてやればいい コメント 座標の変換はいいね！わりと感動した。 座標を変換する時は、保存させたい事を考え… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20121213%2F1355334312" title="SRM 206 DIV1 Hard HexagonIntersections - antaの競技プログラミング練習日記" 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 2012-12-13 02:45:12 rich https://anta1.hatenadiary.org/entry/20121213/1355334312 1.0 100%