JOI難易度６ JOIポスター

問題原文

https://imoz.jp/data/joi/2013-sp-d1-joi_poster.pdf

問題要旨

縦 , 横 のポスター上に 個の点が並んでいる。
これらのうち異なるものを４つ選び、それぞれa, b, c, d とするとき、以下の条件を満たすようなものはいくつあるか？

• a を中心とし、bを通るような円が、 cを中心とし、dを通るような円を含む（重なってはダメ）

• どちらの円も、ポスターからはみ出さない

• 

解法

４点選ぶ全探索。
atcoder.jp

とベースは一緒。

ただし、比較において丸め誤差で落ちる可能性があるので、整数として計算する必要がある。

atcoder.jp

と一緒。

が、僕は学習しない生き物なので見事に丸め誤差で爆発した。（は？？？？？？w） 頭モンチッチか〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜？？？？？？？？？？？？？っっっっっっwシンバルバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンw バァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンwバァンw

実装

関数化するとデバッグしやすいかもしれない。
ギリギリだったのでPyPy2で無理やり通した。枝刈りは大事。

def main():
    import sys
    from math import sqrt
    my_input = sys.stdin.readline
    N, W, H = map(int, my_input().split())
    P = [tuple(map(int, my_input().split())) for _ in range(N)]


    def dist2x(p1, p2):
        return pow((p1[0] - p2[0]), 2) + pow((p1[1] - p2[1]), 2)


    def inside(p1, p2):
        d12 = sqrt(dist2x(p1, p2))
        x1, y1 = p1
        if (x1 + d12 <= W) and (0 <= x1 - d12) and (y1 + d12 <= H) and (0 <= y1 - d12):
            return True
        else:
            return False


    def inclusive(p1, p2, p3, p4):
        d12 = dist2x(p1, p2)
        d34 = dist2x(p3, p4)
        d13 = dist2x(p1, p3)

        if d12 - d34 - d13 < 0:
            return 0

        return pow(d12 - d34 - d13, 2) > 4 * d34 * d13


    ans = 0
    for p1 in P:
        for p2 in P:
            if not inside(p1, p2):
                continue

            for p3 in P:
                for p4 in P:
                    if len(set([p1, p2, p3, p4])) != 4:
                        continue

                    if not inside(p3, p4):
                        continue

                    ans += inclusive(p1, p2, p3, p4)

    print(ans)


if __name__ == '__main__':
    main()

感想

反省！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！いやっほおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお

学習をしていけおれはもんちっちだ