結果

問題 No.2909 Imaginary Summer
ユーザー 👑 p-adicp-adic
提出日時 2024-09-27 14:57:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,630 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 82,120 KB
実行使用メモリ 159,852 KB
最終ジャッジ日時 2024-10-02 17:40:23
合計ジャッジ時間 78,465 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4,043 ms
78,032 KB
testcase_01 AC 4,041 ms
78,556 KB
testcase_02 AC 4,039 ms
78,188 KB
testcase_03 AC 4,039 ms
78,440 KB
testcase_04 AC 4,038 ms
78,304 KB
testcase_05 AC 4,039 ms
78,320 KB
testcase_06 AC 4,049 ms
78,880 KB
testcase_07 AC 4,040 ms
78,416 KB
testcase_08 AC 4,038 ms
78,732 KB
testcase_09 AC 4,686 ms
159,852 KB
testcase_10 AC 4,535 ms
145,776 KB
testcase_11 AC 4,555 ms
149,920 KB
testcase_12 AC 4,659 ms
155,880 KB
testcase_13 AC 4,293 ms
141,264 KB
testcase_14 AC 4,417 ms
141,024 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
import time
import random
import math
def TwoDimensionalAllNearestNeighbourRandomised(d2,S,T,bucket_size,time_bound):
	S_size = len(S); T_size = len(T)
	if S_size == 0:return[]
	assert( T_size > 0 )
	nn = [set()for i in R(S_size)]
	for i in R(S_size):nn[i].add(0)
	line = [0]*T_size
	now = time.time()
	time_bound /= 1000
	while time.time() - now < time_bound:
		theta = random.randint( -1000 , 1000 ) * 0.00314
		dx = math.cos( theta ); dy = math.sin( theta )
		def proj( v ):return v[0] * dx + v[1] * dy
		for j in R(T_size):line[j] = [ proj( T[j] ) , j ]
		line.sort()
		line_ord = [0]*T_size
		for i in R(S_size):
			proj_i = [ proj( S[i] ) , 0 ]
			l , r = 0 , T_size
			while l + 1 < r:
				m = ( l + r ) >> 1
				if proj_i < line[m]:r = m
				else:l = m
			j_min = max( 0 , l - bucket_size )
			j_ulim = min( T_size , l + bucket_size + 1 )
			d_opt = d2( S[i] , T[next( iter( nn[i] ) )] )
			for j in R(j_min,j_ulim):
				d_temp = d2( S[i] , T[line[j][1]] )
				if d_opt > d_temp:
					d_opt = d_temp
					nn[i] = set(); nn[i].add( line[j][1] )
				elif d_opt == d_temp and not line[j][1] in nn[i]:
					nn[i].add( line[j][1] )
	return[list(nn[i])for i in R(S_size)]

def d2(u,v):return (u[0]-v[0])**2+(u[1]-v[1])**2

J=lambda:list(map(int,input().split()))
N,M,K=J()
N+=1
XY=[J()for i in R(N)]
AB=[J()for k in R(K)]
d=min(d2(XY[0],XY[i])for i in R(1,N))**0.5
ann1=TwoDimensionalAllNearestNeighbourRandomised(d2,AB,XY,1000,2000)
ann2=TwoDimensionalAllNearestNeighbourRandomised(d2,AB,XY,17,2000)
answer=sum(min(d2(XY[0],AB[k])**0.5,min(d+d2(XY[i],AB[k])**0.5 for i in ann1[k]+ann2[k]))for k in R(K))
print(answer*2)
0