結果
問題 | No.2769 Number of Rhombi |
ユーザー | dp_ijk |
提出日時 | 2024-06-18 01:26:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,097 ms / 5,000 ms |
コード長 | 707 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 328,760 KB |
最終ジャッジ日時 | 2024-06-18 01:27:27 |
合計ジャッジ時間 | 26,542 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from collections import defaultdict from collections import Counter from math import gcd N = int(input()) XY = [tuple(map(int, input().split())) for _ in range(N)] d = defaultdict(Counter) for i in range(N): x, y = XY[i] for j in range(i+1, N): a, b = XY[j] dx, dy = a-x, b-y if dx < 0: dx, dy = -(dx), -(dy) if dx == 0 and dy < 0: dy = -(dy) g = gcd(dx, dy) dx, dy = dx//g, dy//g center = (x+a, b+y) d[center][dx, dy] += 1 ans = 0 for center, C in d.items(): for (dx, dy), cnt in C.items(): if dy > 0: ndx, ndy = dy, -dx else: ndx, ndy = -dy, dx ans += cnt * C[ndx, ndy] ans //= 2 print(ans)