結果

問題 No.2769 Number of Rhombi
ユーザー ButterflvButterflv
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import math
import random
mod=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 = 0
N=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]: continue
x1, 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)
# vec
vec = [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]*=-1
g = 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]+=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]: continue
x1, 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)
# vec
vec = [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]*=-1
g = 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]+=1
inv_vec = [vec[1], vec[0]*(-1)]
if inv_vec[1]<0:
inv_vec[0]*=-1; inv_vec[1]*=-1
if 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_x
c,d=tyuten_y
e,f=inv_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:
ans += point_info[hush]
print(ans//8 if ans!=0 else 0)
# print(point_info)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0