結果

問題 No.2438 Double Least Square
ユーザー lam6er
提出日時 2025-04-15 22:29:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,032 bytes
コンパイル時間 430 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 76,536 KB
最終ジャッジ日時 2025-04-15 22:31:27
合計ジャッジ時間 2,923 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    H = int(input[ptr])
    ptr += 1
    points = []
    for _ in range(N):
        x = int(input[ptr])
        y = int(input[ptr + 1])
        points.append((x, y))
        ptr += 2

    min_L = float('inf')

    # Define different initial assignment strategies
    initializations = [
        [True] * N,  # All points in F
        [False] * N,  # All points in G
        [(y > H) for (x, y) in points],  # y > H
        [(y > H / 2) for (x, y) in points],  # y > H/2
        [(y < H) for (x, y) in points],  # y < H
        [((y - H) ** 2 < y ** 2) for (x, y) in points],  # Compare (y-H)^2 vs y^2
    ]

    for initial_F in initializations:
        current_L = compute_optimal_L(points, H, initial_F)
        if current_L < min_L:
            min_L = current_L

    print("{0:.20f}".format(min_L))

def compute_optimal_L(points, H, initial_F):
    N = len(points)
    F = initial_F.copy()
    prev_F = None

    while prev_F != F:
        prev_F = F.copy()

        sum_xi_sq_F = 0.0
        sum_xi_yi_minus_H_F = 0.0
        sum_xi_sq_G = 0.0
        sum_xi_yi_G = 0.0

        for i in range(N):
            x, y = points[i]
            if F[i]:
                sum_xi_sq_F += x * x
                sum_xi_yi_minus_H_F += x * (y - H)
            else:
                sum_xi_sq_G += x * x
                sum_xi_yi_G += x * y

        a1 = sum_xi_yi_minus_H_F / sum_xi_sq_F if sum_xi_sq_F != 0 else 0.0
        a2 = sum_xi_yi_G / sum_xi_sq_G if sum_xi_sq_G != 0 else 0.0

        new_F = []
        for x, y in points:
            error_f = (y - (a1 * x + H)) ** 2
            error_g = (y - (a2 * x)) ** 2
            new_F.append(error_f <= error_g)

        F = new_F

    L = 0.0
    for i in range(N):
        x, y = points[i]
        if F[i]:
            term = (y - (a1 * x + H)) ** 2
        else:
            term = (y - (a2 * x)) ** 2
        L += term

    return L

if __name__ == '__main__':
    main()
0