結果

問題 No.2769 Number of Rhombi
ユーザー ButterflvButterflv
提出日時 2024-05-31 23:14:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,494 ms / 5,000 ms
コード長 2,726 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 175,364 KB
最終ジャッジ日時 2024-05-31 23:15:25
合計ジャッジ時間 59,118 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
55,148 KB
testcase_01 AC 41 ms
56,080 KB
testcase_02 AC 46 ms
55,920 KB
testcase_03 AC 1,663 ms
145,784 KB
testcase_04 AC 1,503 ms
139,072 KB
testcase_05 AC 1,294 ms
118,116 KB
testcase_06 AC 1,624 ms
133,328 KB
testcase_07 AC 2,169 ms
153,836 KB
testcase_08 AC 1,562 ms
144,908 KB
testcase_09 AC 2,009 ms
152,316 KB
testcase_10 AC 1,678 ms
153,436 KB
testcase_11 AC 1,845 ms
157,524 KB
testcase_12 AC 2,002 ms
166,252 KB
testcase_13 AC 1,734 ms
166,980 KB
testcase_14 AC 1,851 ms
163,348 KB
testcase_15 AC 2,255 ms
171,156 KB
testcase_16 AC 1,669 ms
163,132 KB
testcase_17 AC 2,420 ms
174,728 KB
testcase_18 AC 2,318 ms
175,024 KB
testcase_19 AC 1,531 ms
161,420 KB
testcase_20 AC 1,551 ms
161,932 KB
testcase_21 AC 2,163 ms
169,656 KB
testcase_22 AC 1,746 ms
163,180 KB
testcase_23 AC 1,676 ms
162,464 KB
testcase_24 AC 40 ms
54,992 KB
testcase_25 AC 1,498 ms
158,928 KB
testcase_26 AC 1,588 ms
158,908 KB
testcase_27 AC 1,637 ms
161,776 KB
testcase_28 AC 2,494 ms
175,364 KB
testcase_29 AC 1,781 ms
163,976 KB
testcase_30 AC 1,719 ms
161,916 KB
testcase_31 AC 1,461 ms
158,336 KB
testcase_32 AC 1,683 ms
147,464 KB
testcase_33 AC 1,584 ms
145,044 KB
testcase_34 AC 1,748 ms
152,040 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0