結果

問題 No.1874 Minimum of Sum of Rectangles
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:48:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,012 ms / 3,000 ms
コード長 1,574 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 129,896 KB
最終ジャッジ日時 2025-03-26 15:50:04
合計ジャッジ時間 25,860 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

if n == 0:
    print(0)
    exit()

# Extract x and y coordinates
sorted_x = sorted(x for x, y in points)
sorted_y = sorted(y for x, y in points)

# Determine initial medians
if n % 2 == 1:
    qx = sorted_x[n // 2]
    qy = sorted_y[n // 2]
else:
    qx = sorted_x[(n // 2) - 1]
    qy = sorted_y[(n // 2) - 1]

prev_qx, prev_qy = None, None

# Iterate until convergence
while (qx, qy) != (prev_qx, prev_qy):
    prev_qx, prev_qy = qx, qy

    # Compute new_qy based on current qx
    a = [abs(x - qx) for x, y in points]
    y_list = sorted(zip([y for x, y in points], a), key=lambda t: t[0])
    total_a = sum(a)
    new_qy = None

    if total_a == 0:
        new_qy = y_list[0][0] if y_list else 0
    else:
        target = total_a / 2
        cum = 0
        for y, w in y_list:
            cum += w
            if cum >= target:
                new_qy = y
                break

    # Compute new_qx based on new_qy
    b = [abs(y - new_qy) for x, y in points]
    x_list = sorted(zip([x for x, y in points], b), key=lambda t: t[0])
    total_b = sum(b)
    new_qx = None

    if total_b == 0:
        new_qx = x_list[0][0] if x_list else 0
    else:
        target_x = total_b / 2
        cum_x = 0
        for x, w in x_list:
            cum_x += w
            if cum_x >= target_x:
                new_qx = x
                break

    qx, qy = new_qx, new_qy

# Calculate the minimal sum
total_sum = 0
for x, y in points:
    total_sum += abs(x - qx) * abs(y - qy)

print(total_sum)
0