結果

問題 No.2438 Double Least Square
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:54:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,636 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 72,296 KB
最終ジャッジ日時 2025-06-12 19:55:07
合計ジャッジ時間 3,272 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    a1 = 0.0
    a2 = 0.0
    epsilon = 1e-8
    max_iter = 100000
    iter = 0

    while iter < max_iter:
        S = []
        T = []
        for x, y in points:
            f_val = a1 * x + H
            f_sq = (y - f_val) ** 2
            g_val = a2 * x
            g_sq = (y - g_val) ** 2
            if f_sq <= g_sq:
                S.append((x, y))
            else:
                T.append((x, y))

        sum_S_x = 0.0
        sum_S_x2 = 0.0
        sum_S_yx = 0.0
        for x, y in S:
            sum_S_x += x
            sum_S_x2 += x * x
            sum_S_yx += y * x

        new_a1 = a1
        if sum_S_x2 != 0:
            numerator = sum_S_yx - H * sum_S_x
            new_a1 = numerator / sum_S_x2

        sum_T_x2 = 0.0
        sum_T_yx = 0.0
        for x, y in T:
            sum_T_x2 += x * x
            sum_T_yx += y * x

        new_a2 = a2
        if sum_T_x2 != 0:
            new_a2 = sum_T_yx / sum_T_x2

        if abs(new_a1 - a1) < epsilon and abs(new_a2 - a2) < epsilon:
            break

        a1 = new_a1
        a2 = new_a2
        iter += 1

    L = 0.0
    for x, y in points:
        f_val = a1 * x + H
        f_sq = (y - f_val) ** 2
        g_val = a2 * x
        g_sq = (y - g_val) ** 2
        L += min(f_sq, g_sq)

    print("{0:.10f}".format(L))

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