JOI難易度6 JOIポスター
問題原文
https://imoz.jp/data/joi/2013-sp-d1-joi_poster.pdf
問題要旨
縦 , 横
のポスター上に
個の点が並んでいる。
これらのうち異なるものを4つ選び、それぞれa, b, c, d とするとき、以下の条件を満たすようなものはいくつあるか?
- a を中心とし、bを通るような円が、 cを中心とし、dを通るような円を含む(重なってはダメ)
どちらの円も、ポスターからはみ出さない
解法
4点選ぶ全探索。
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()
感想
反省!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!いやっほおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
学習をしていけおれはもんちっちだ