結果

問題 No.1874 Minimum of Sum of Rectangles
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:31:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,725 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 82,976 KB
実行使用メモリ 116,140 KB
最終ジャッジ日時 2025-03-31 17:32:36
合計ジャッジ時間 13,444 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    x_list = []
    y_list = []
    for _ in range(n):
        x = int(input[idx])
        y = int(input[idx+1])
        x_list.append(x)
        y_list.append(y)
        idx +=2
    
    def get_candidates(arr):
        arr_sorted = sorted(arr)
        m = len(arr_sorted)
        # Generate indices around the median
        candidates = set()
        if m ==0:
            return []
        # Median positions
        if m %2 ==1:
            mid = m//2
            indices = [mid]
        else:
            mid_left = (m//2)-1
            mid_right = m//2
            indices = [mid_left, mid_right]
        # Extend around the median indices
        for i in indices:
            for delta in range(-5,6):
                idx_candidate = i + delta
                if 0 <= idx_candidate < m:
                    candidates.add(arr_sorted[idx_candidate])
        # Also add the elements at start and end in case of sparse distribution
        candidates.add(arr_sorted[0])
        candidates.add(arr_sorted[-1])
        return list(candidates)
    
    x_candidates = get_candidates(x_list)
    y_candidates = get_candidates(y_list)
    
    min_sum = float('inf')
    
    for x in x_candidates:
        for y in y_candidates:
            current_sum = 0
            for i in range(n):
                xi = x_list[i]
                yi = y_list[i]
                if xi ==x or yi ==y:
                    continue
                current_sum += abs(xi -x) * abs(yi - y)
            if current_sum < min_sum:
                min_sum = current_sum
    
    print(min_sum)

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