結果
問題 | No.2769 Number of Rhombi |
ユーザー |
|
提出日時 | 2024-05-31 23:14:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,427 ms / 5,000 ms |
コード長 | 2,726 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 174,688 KB |
最終ジャッジ日時 | 2024-12-21 01:33:08 |
合計ジャッジ時間 | 61,392 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
import mathimport randommod=random.randint(1<<50,1<<60)B=random.randint(1<<50,1<<60)while math.gcd(B,mod)!=1: B=random.randint(1<<50,1<<60)base = [pow(B,i,mod) for i in range(10)]ans = 0N=int(input())P = []for i in range(N):x, y = map(int, input().split())P.append((x, y))point_info = dict()for i in range(N):for j in range(N):if P[i]==P[j]: continuex1, y1 = P[i]x2, y2 = P[j]if (x1+x2)%2==0:tyuten_x = ((x1+x2)//2, 1)else:tyuten_x = (x1+x2, 2)if (y1+y2)%2==0:tyuten_y = ((y1+y2)//2, 1)else:tyuten_y = (y1+y2, 2)# 方向 vecvec = [x1-x2, y1-y2]if x1-x2==0:vec[1] = abs(vec[1])if y1-y2==0:vec[0] = abs(vec[0])if vec[1]<0: vec[0]*=-1; vec[1]*=-1g = math.gcd(abs(vec[0]), abs(vec[1]))vec[0]//=g; vec[1]//=g# vec = tuple(vec)a,b=tyuten_xc,d=tyuten_ye,f=vechush = ((a*base[0] + b*base[1] + c*base[2] +d*base[3] + e*base[4] + f*base[5])%mod)if point_info.get(hush)==None:point_info[hush]=0point_info[hush]+=1# if point_info.get((tyuten, vec))==None:# point_info[(tyuten, vec)] = 0# point_info[(tyuten, vec)] += 1# for key in point_info:# point_info[key]=dict(point_info[key])# point_info = dict(point_info)# for key in point_info:# print(key, point_info[key])for i in range(N):for j in range(N):if P[i]==P[j]: continuex1, y1 = P[i]x2, y2 = P[j]if (x1+x2)%2==0:tyuten_x = ((x1+x2)//2, 1)else:tyuten_x = (x1+x2, 2)if (y1+y2)%2==0:tyuten_y = ((y1+y2)//2, 1)else:tyuten_y = (y1+y2, 2)# 方向 vecvec = [x1-x2, y1-y2]if x1-x2==0:vec[1] = abs(vec[1])if y1-y2==0:vec[0] = abs(vec[0])if vec[1]<0: vec[0]*=-1; vec[1]*=-1g = math.gcd(abs(vec[0]), abs(vec[1]))vec[0]//=g; vec[1]//=g# vec = tuple(vec)# a,b=tyuten_x# c,d=tyuten_y# e,f=vec# hush = ((# a*base[0] + b*base[1] + c*base[2] +# d*base[3] + e*base[4] + f*base[5]# )%mod)# if point_info.get(hush)==None:# point_info[hush]=0# point_info[hush]+=1inv_vec = [vec[1], vec[0]*(-1)]if inv_vec[1]<0:inv_vec[0]*=-1; inv_vec[1]*=-1if inv_vec[0]==0:inv_vec[1] = abs(inv_vec[1])if inv_vec[1]==0:inv_vec[0] = abs(inv_vec[0])inv_vec = tuple(inv_vec)a,b=tyuten_xc,d=tyuten_ye,f=inv_vechush = ((a*base[0] + b*base[1] + c*base[2] +d*base[3] + e*base[4] + f*base[5])%mod)if point_info.get(hush)!=None:ans += point_info[hush]print(ans//8 if ans!=0 else 0)# print(point_info)