結果

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

ソースコード

diff # 

def compute_min(points, H, initial_assign):
    assignment = initial_assign.copy()
    prev_assignment = None
    n = len(points)
    while assignment != prev_assignment:
        prev_assignment = assignment.copy()
        # Compute S and T
        S = []
        T = []
        for i in range(n):
            if assignment[i]:
                S.append(points[i])
            else:
                T.append(points[i])
        
        # Compute a1
        sum_xi2_S = sum(xi * xi for xi, yi in S)
        sum_xy_S = sum(xi * yi for xi, yi in S)
        sum_Hx_S = sum(H * xi for xi, yi in S)
        a1 = (sum_xy_S - sum_Hx_S) / sum_xi2_S if sum_xi2_S != 0 else 0.0
        
        # Compute a2
        sum_xi2_T = sum(xi * xi for xi, yi in T)
        sum_xy_T = sum(xi * yi for xi, yi in T)
        a2 = sum_xy_T / sum_xi2_T if sum_xi2_T != 0 else 0.0
        
        # Reassign points
        new_assignment = []
        for xi, yi in points:
            error_f = (yi - (a1 * xi + H)) ** 2
            error_g = (yi - a2 * xi) ** 2
            new_assignment.append(error_f < error_g)
        assignment = new_assignment
    
    # Calculate the total error
    total = 0.0
    for xi, yi in points:
        error_f = (yi - (a1 * xi + H)) ** 2
        error_g = (yi - a2 * xi) ** 2
        total += min(error_f, error_g)
    return total

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
    
    # Try two different initial assignments
    initial_assign1 = [ (yi > H / 2) for xi, yi in points ]
    initial_assign2 = [ (yi <= H / 2) for xi, yi in points ]
    
    sum1 = compute_min(points, H, initial_assign1)
    sum2 = compute_min(points, H, initial_assign2)
    
    min_sum = min(sum1, sum2)
    
    # Also try all points assigned to f and all to g
    # Initial assign all to f
    initial_assign3 = [True] * N
    sum3 = compute_min(points, H, initial_assign3)
    min_sum = min(min_sum, sum3)
    
    # Initial assign all to g
    initial_assign4 = [False] * N
    sum4 = compute_min(points, H, initial_assign4)
    min_sum = min(min_sum, sum4)
    
    # Print with sufficient precision
    print("{0:.20f}".format(min_sum).rstrip('0').rstrip('.') if '.' in "{0:.20f}".format(min_sum) else "{0:.20f}".format(min_sum))

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