結果

問題 No.1874 Minimum of Sum of Rectangles
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:37:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,081 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 115,196 KB
最終ジャッジ日時 2025-03-31 17:38:02
合計ジャッジ時間 27,188 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    if n == 0:
        print(0)
        return
    points = []
    idx = 1
    for _ in range(n):
        x, y = int(input[idx]), int(input[idx + 1])
        points.append((x, y))
        idx += 2
    
    sorted_x = sorted(points, key=lambda p: (p[0], p[1]))
    sorted_y = sorted(points, key=lambda p: (p[1], p[0]))
    
    # Initial x and y as medians of x and y coordinates
    mid = n // 2
    if n % 2 == 1:
        x0 = sorted_x[mid][0]
        y0 = sorted_y[mid][1]
    else:
        x0 = sorted_x[mid - 1][0]
        y0 = sorted_y[mid - 1][1]
    
    min_sum = sum(abs(x0 - xi) * abs(y0 - yi) for (xi, yi) in points)
    
    # Iterate to improve x and y
    for _ in range(20):
        # Compute new x based on y0
        weights = [abs(y0 - yi) for (xi, yi) in sorted_x]
        total_weight = sum(weights)
        if total_weight == 0:
            new_x = x0
        else:
            half = total_weight / 2
            cum = 0
            new_x = x0  # Default in case of issues
            for i in range(len(sorted_x)):
                xi, yi = sorted_x[i]
                cum += weights[i]
                if cum >= half:
                    new_x = xi
                    break
        
        # Compute new y based on new_x
        weights = [abs(new_x - xi) for (xi, yi) in sorted_y]
        total_weight = sum(weights)
        if total_weight == 0:
            new_y = y0
        else:
            half = total_weight / 2
            cum = 0
            new_y = y0  # Default
            for i in range(len(sorted_y)):
                xi, yi = sorted_y[i]
                cum += weights[i]
                if cum >= half:
                    new_y = yi
                    break
        
        current_sum = 0
        for (xi, yi) in points:
            current_sum += abs(new_x - xi) * abs(new_y - yi)
        if current_sum < min_sum:
            min_sum = current_sum
        
        x0, y0 = new_x, new_y
    
    print(min_sum)

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