結果

問題 No.180 美しいWhitespace (2)
ユーザー lam6er
提出日時 2025-04-15 23:58:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,950 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 65,960 KB
最終ジャッジ日時 2025-04-16 00:00:09
合計ジャッジ時間 2,420 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def compute_upper_hull(lines):
    hull = []
    for a, b in lines:
        while len(hull) >= 2:
            a1, b1 = hull[-2]
            a2, b2 = hull[-1]
            if b1 == b2:
                if a2 >= a1:
                    hull.pop()
                else:
                    break
                continue
            x_prev = (a2 - a1) / (b1 - b2)
            if b == b2:
                if a > a2:
                    hull.pop()
                else:
                    break
                continue
            x_curr = (a - a2) / (b2 - b)
            if x_curr <= x_prev:
                hull.pop()
            else:
                break
        hull.append((a, b))
    return hull

def compute_lower_hull(lines):
    hull = []
    for a, b in lines:
        while len(hull) >= 2:
            a1, b1 = hull[-2]
            a2, b2 = hull[-1]
            if b1 == b2:
                if a2 <= a1:
                    hull.pop()
                else:
                    break
                continue
            x_prev = (a2 - a1) / (b1 - b2)
            if b == b2:
                if a < a2:
                    hull.pop()
                else:
                    break
                continue
            x_curr = (a - a2) / (b2 - b)
            if x_curr <= x_prev:
                hull.pop()
            else:
                break
        hull.append((a, b))
    return hull

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    original_lines = []
    for _ in range(N):
        a = int(input[ptr])
        b = int(input[ptr+1])
        original_lines.append((a, b))
        ptr += 2
    
    # Process upper envelope
    upper_dict = {}
    for a, b in original_lines:
        if b in upper_dict:
            if a > upper_dict[b]:
                upper_dict[b] = a
        else:
            upper_dict[b] = a
    upper_lines = sorted([(a, b) for b, a in upper_dict.items()], key=lambda x: -x[1])
    upper_hull = compute_upper_hull(upper_lines)
    
    # Process lower envelope
    lower_dict = {}
    for a, b in original_lines:
        if b in lower_dict:
            if a < lower_dict[b]:
                lower_dict[b] = a
        else:
            lower_dict[b] = a
    lower_lines = sorted([(a, b) for b, a in lower_dict.items()], key=lambda x: x[1])
    lower_hull = compute_lower_hull(lower_lines)
    
    # Collect critical x's
    critical_x = []
    
    # Upper hull critical points
    for i in range(len(upper_hull) - 1):
        a1, b1 = upper_hull[i]
        a2, b2 = upper_hull[i+1]
        if b1 == b2:
            continue
        x = (a2 - a1) / (b1 - b2)
        if x > 0:
            critical_x.append(x)
    
    # Lower hull critical points
    for i in range(len(lower_hull) - 1):
        a1, b1 = lower_hull[i]
        a2, b2 = lower_hull[i+1]
        if b1 == b2:
            continue
        x = (a2 - a1) / (b1 - b2)
        if x > 0:
            critical_x.append(x)
    
    # Generate candidate x's
    candidates = {1}
    for x in critical_x:
        if x <= 0:
            continue
        floor_x = math.floor(x)
        ceil_x = math.ceil(x)
        candidates.add(floor_x)
        candidates.add(ceil_x)
        if x == floor_x:
            candidates.add(int(x))
    
    # Compute f(x) for each candidate x
    min_f = float('inf')
    best_x = None
    for x in sorted(candidates):
        if x <= 0:
            continue
        current_max = -float('inf')
        current_min = float('inf')
        for a, b in original_lines:
            val = a + b * x
            if val > current_max:
                current_max = val
            if val < current_min:
                current_min = val
        f = current_max - current_min
        if f < min_f or (f == min_f and (best_x is None or x < best_x)):
            min_f = f
            best_x = x
    print(best_x)

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