結果

問題 No.2438 Double Least Square
ユーザー gew1fw
提出日時 2025-06-12 14:36:45
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,898 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 71,148 KB
最終ジャッジ日時 2025-06-12 14:36:49
合計ジャッジ時間 2,758 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 14
権限があれば一括ダウンロードができます

ソースコード

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]); idx +=1
        y = int(input[idx]); idx +=1
        points.append( (x, y) )
    
    # Initialize a1 and a2 to 0
    a1 = 0.0
    a2 = 0.0
    
    max_iter = 1000
    tolerance = 1e-8
    converged = False
    
    for _ in range(max_iter):
        f_group = []
        g_group = []
        
        for x, y in points:
            e_f = (y - a1 * x - H) ** 2
            e_g = (y - a2 * x) ** 2
            if e_f < e_g:
                f_group.append( (x, y) )
            else:
                g_group.append( (x, y) )
        
        # Compute new_a1
        sum_f_num = 0.0
        sum_f_den = 0.0
        for x, y in f_group:
            sum_f_num += (y - H) * x
            sum_f_den += x ** 2
        if sum_f_den != 0:
            new_a1 = sum_f_num / sum_f_den
        else:
            new_a1 = a1
        
        # Compute new_a2
        sum_g_num = 0.0
        sum_g_den = 0.0
        for x, y in g_group:
            sum_g_num += y * x
            sum_g_den += x ** 2
        if sum_g_den != 0:
            new_a2 = sum_g_num / sum_g_den
        else:
            new_a2 = a2
        
        # Check convergence
        if abs(new_a1 - a1) < tolerance and abs(new_a2 - a2) < tolerance:
            a1 = new_a1
            a2 = new_a2
            converged = True
            break
        
        a1 = new_a1
        a2 = new_a2
    
    if not converged:
        # After max_iter, use the last a1 and a2
        pass
    
    # Compute L
    total_L = 0.0
    for x, y in points:
        e_f = (y - a1 * x - H) ** 2
        e_g = (y - a2 * x) ** 2
        total_L += min(e_f, e_g)
    
    print("{0:.11f}".format(total_L))

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