結果
問題 | No.2438 Double Least Square |
ユーザー |
|
提出日時 | 2023-08-19 01:33:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 415 ms / 2,000 ms |
コード長 | 3,254 bytes |
コンパイル時間 | 126 ms |
コンパイル使用メモリ | 82,528 KB |
実行使用メモリ | 78,644 KB |
最終ジャッジ日時 | 2024-11-28 14:03:01 |
合計ジャッジ時間 | 8,004 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import sysfrom itertools import permutationsfrom heapq import *from math import acosinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())def solve(N,H,point):def calc_min(a,b,c):if a == 0:return 0t = -b/(2*a)return a*t*t+b*t+carg = []for i in range(N):x,y = point[i]r = ((y-H/2)**2 + x**2)**.5arg.append(acos((H/2-y)/r))idx = [i for i in range(N)]idx.sort(key=lambda i:arg[i])i_to_pos = [-1] * Nfor i in range(N):i_to_pos[idx[i]] = iX_idx = [i for i in range(N)]X_idx.sort(key=lambda i:point[i][0])ans = 10**100for i in range(N+1):up = [idx[j] for j in range(i,N)]down = [idx[j] for j in range(i)]fp,fq,fr = 0,0,0gp,gq,gr = 0,0,0for j in up:x,y = point[j]gp += x*xgq += 2 * x * (-y)gr += y*yfor j in down:x,y = point[j]fp += x*xfq += 2 * x * (H-y)fr += (H-y) * (H-y)tmp = calc_min(fp,fq,fr) + calc_min(gp,gq,gr)ans = min(ans,tmp)for j in X_idx:x,y = point[j]if i <= i_to_pos[j]:gp -= x*xgq -= 2 * x * (-y)gr -= y*yfp += x*xfq += 2 * x * (H-y)fr += (H-y) * (H-y)else:gp += x*xgq += 2 * x * (-y)gr += y*yfp -= x*xfq -= 2 * x * (H-y)fr -= (H-y) * (H-y)tmp = calc_min(fp,fq,fr) + calc_min(gp,gq,gr)ans = min(ans,tmp)return ansdef brute(N,H,point):def calc(f,g):res = 0a,b,c = 0,0,0for i in f:x,y = point[i]a += x*xb += 2*x*(H-y)c += (H-y)*(H-y)if a!=0:t = (-b/(2*a))res += a * t * t + b * t + ca,b,c = 0,0,0for i in g:x,y = point[i]a += x*xb -= 2 * x * yc += y*yif a!=0:t = (-b/(2*a))res += a * t * t + b * t + creturn resans = 10**100for S in range(1<<N):f = [i for i in range(N) if S>>i & 1]g = [i for i in range(N) if S>>i & 1 == 0]ans = min(ans,calc(f,g))#print(calc(f,g),f,g)return ansimport randomwhile False:N = random.randint(3,10)H = random.randint(1,10)point = []for i in range(N):x,y = [random.randint(1,10) for _ in range(2)]point.append((x,y))#N,H = 3,10#point = [(4,7),(2,7),(4,5)]res = solve(N,H,point)exp = brute(N,H,point)if abs(res-exp) > 10**-2:print("WA")print(N)print(H)for x,y in point:print(x,y)print("res:",res)print("exp:",exp)exit()else:print("AC")N = int(input())H = int(input())point = [tuple(mi()) for i in range(N)]print(solve(N,H,point))