結果

問題 No.2909 Imaginary Summer
ユーザー 👑 p-adic
提出日時 2024-09-27 16:29:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,674 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 138,616 KB
最終ジャッジ日時 2024-10-02 17:43:12
合計ジャッジ時間 76,557 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 4 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
import time
import random
import math
def TwoDimensionalAllNearestNeighbourRandomisedDouble(d,S,T,bucket_size,time_bound):
	S_size = len(S); T_size = len(T)
	if S_size == 0:return[]
	assert( T_size > 0 )
	answer = [0]*S_size
	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()
		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_llim = max( -1 , l - bucket_size - 1 )
			j_ulim = min( T_size , l + bucket_size + 1 )
			d_opt = d( S[i] , T[answer[i]] )
			for j in R(l-1,j_llim,-1):
				d_temp = d( S[i] , T[line[j][1]] )
				if d_opt > d_temp:
					d_opt = d_temp
					answer[i] = line[j][1]
				elif abs( line[j][0] - proj_i[0] ) > d_opt:break
			for j in R(l,j_ulim):
				d_temp = d( S[i] , T[line[j][1]] )
				if d_opt > d_temp:
					d_opt = d_temp
					answer[i] = line[j][1]
				elif abs( line[j][0] - proj_i[0] ) > d_opt:break
	return answer

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

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(D(XY[0],XY[i])for i in R(1,N))
ann1=TwoDimensionalAllNearestNeighbourRandomisedDouble(D,AB,XY,100,2000)
ann2=TwoDimensionalAllNearestNeighbourRandomisedDouble(D,AB,XY,17,2000)
answer=sum(min(D(XY[0],AB[k]),d+D(XY[ann1[k]],AB[k]),d+D(XY[ann2[k]],AB[k]))for k in R(K))
print(answer*2)
0