結果
問題 | No.2355 Unhappy Back Dance |
ユーザー |
👑 ![]() |
提出日時 | 2023-06-16 22:53:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,385 ms / 6,000 ms |
コード長 | 1,417 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,696 KB |
実行使用メモリ | 264,940 KB |
最終ジャッジ日時 | 2024-06-24 15:54:11 |
合計ジャッジ時間 | 46,162 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import sys import math input = sys.stdin.readline def read_values(): return map(int, input().split()) def read_index(): return map(lambda x: int(x) - 1, input().split()) def read_list(): return list(read_values()) def read_lists(N): return [read_list() for _ in range(N)] def main(): n=int(input()) x=[0]*n y=[0]*n for i in range(n): x[i],y[i]=read_values() uh=[0]*n for i in range(n): mp=dict() for j in range(n): dx=y[i]-y[j] dy=-x[i]+x[j] dc=-(dx*x[i]+dy*y[i]) g=math.gcd(dx,dy,dc) if dx<0 or (dx==0 and dy<0): g*=-1 if g==0: continue dx//=g dy//=g dc//=g ad=dx+dy*(10**18+1)+dc*(10**18+1)*(2*(10**18)+1) if not ad in mp: mp[ad]=set() mp[ad].add(j) for vc in mp.values(): if len(vc) < 2: continue if len(vc) > 2: for v in vc: uh[v]|=1 continue vl=list(vc) vl.append(i) for j in range(3): inner = (x[vl[(j+2)%3]]-x[vl[j]])*(x[vl[(j+1)%3]]-x[vl[j]])+(y[vl[(j+2)%3]]-y[vl[j]])*(y[vl[(j+1)%3]]-y[vl[j]]) if inner > 0: uh[vl[j]]|=1 print(sum(uh)) if __name__ == "__main__": main()