結果

問題 No.2438 Double Least Square
ユーザー chineristACchineristAC
提出日時 2023-08-19 01:33:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 427 ms / 2,000 ms
コード長 3,254 bytes
コンパイル時間 609 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 78,664 KB
最終ジャッジ日時 2024-05-06 08:43:11
合計ジャッジ時間 8,812 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,296 KB
testcase_01 AC 41 ms
55,168 KB
testcase_02 AC 43 ms
55,296 KB
testcase_03 AC 43 ms
55,040 KB
testcase_04 AC 43 ms
55,424 KB
testcase_05 AC 44 ms
55,296 KB
testcase_06 AC 43 ms
55,680 KB
testcase_07 AC 46 ms
55,296 KB
testcase_08 AC 47 ms
55,424 KB
testcase_09 AC 45 ms
55,936 KB
testcase_10 AC 347 ms
78,460 KB
testcase_11 AC 348 ms
77,944 KB
testcase_12 AC 346 ms
78,116 KB
testcase_13 AC 349 ms
77,988 KB
testcase_14 AC 346 ms
78,180 KB
testcase_15 AC 358 ms
78,180 KB
testcase_16 AC 356 ms
78,144 KB
testcase_17 AC 359 ms
78,032 KB
testcase_18 AC 364 ms
78,184 KB
testcase_19 AC 364 ms
78,108 KB
testcase_20 AC 339 ms
78,264 KB
testcase_21 AC 335 ms
78,044 KB
testcase_22 AC 319 ms
78,268 KB
testcase_23 AC 348 ms
78,140 KB
testcase_24 AC 350 ms
78,032 KB
testcase_25 AC 315 ms
78,212 KB
testcase_26 AC 340 ms
77,912 KB
testcase_27 AC 352 ms
77,984 KB
testcase_28 AC 356 ms
78,296 KB
testcase_29 AC 427 ms
78,664 KB
testcase_30 AC 42 ms
55,424 KB
testcase_31 AC 43 ms
55,424 KB
testcase_32 AC 43 ms
55,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations
from heapq import *
from math import acos

input = 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 0
        t = -b/(2*a)
        return a*t*t+b*t+c

    arg = []
    for i in range(N):
        x,y = point[i]
        r = ((y-H/2)**2 + x**2)**.5
        arg.append(acos((H/2-y)/r))
    
    idx = [i for i in range(N)]
    idx.sort(key=lambda i:arg[i])

    i_to_pos = [-1] * N
    for i in range(N):
        i_to_pos[idx[i]] = i

    X_idx = [i for i in range(N)]
    X_idx.sort(key=lambda i:point[i][0])

    ans = 10**100

    for 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,0
        gp,gq,gr = 0,0,0

        for j in up:
            x,y = point[j]
            gp += x*x
            gq += 2 * x * (-y)
            gr += y*y
        for j in down:
            x,y = point[j]
            fp += x*x
            fq += 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*x
                gq -= 2 * x * (-y)
                gr -= y*y

                fp += x*x
                fq += 2 * x * (H-y)
                fr += (H-y) * (H-y)
            else:
                gp += x*x
                gq += 2 * x * (-y)
                gr += y*y

                fp -= x*x
                fq -= 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 ans
    

def brute(N,H,point):
    def calc(f,g):
        res = 0

        a,b,c = 0,0,0
        for i in f:
            x,y = point[i]
            a += x*x
            b += 2*x*(H-y)
            c += (H-y)*(H-y)
        if a!=0:
            t = (-b/(2*a))
            
            res += a * t * t + b * t + c

        a,b,c = 0,0,0
        for i in g:
            x,y = point[i]
            a += x*x
            b -= 2 * x * y
            c += y*y
        if a!=0:
            t = (-b/(2*a))
            
            res += a * t * t + b * t + c

        return res

    ans = 10**100

    for 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 ans

import random
while 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))
0