結果

問題 No.2438 Double Least Square
ユーザー chineristAC
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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