TA1SA https://blog.hatena.ne.jp/TA1SA/ TAISA_'s blog https://ta1sa.hatenablog.com/ 幾何パートとデータ構造パートに分かれている問題。幾何パートで下手な考察をして、場合分けと実装を爆発させてしまった。 データ構造パートで解説と違うことをしていたので、主にその部分について整理する。 問題 atcoder.jp 解法 解説にある最初の満点解法の、「aとbを入れ替える」条件を、サイズに依存するようにした解法。 (D1,E1)を点P1、(D2,E2)を点P2とする。また、i番目のドラゴンの位置をp[i]とする。 図を書いて頑張って考えてみる。 すると、各クエリでは、iを種族fの点、jを種族gの点として、(p[i]とP1のなす角,p[i]とP2のなす角)と(p[j]とP1のなす角、p[j… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fta1sa.hatenablog.com%2Fentry%2F2020%2F03%2F11%2F183941" title="JOI&#39;17春合宿 Dragon 2 - TAISA_&#39;s blog" 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 2020-03-11 18:39:41 rich https://ta1sa.hatenablog.com/entry/2020/03/11/183941 1.0 100%