結果

問題 No.180 美しいWhitespace (2)
ユーザー lam6er
提出日時 2025-03-31 17:25:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,899 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 70,936 KB
最終ジャッジ日時 2025-03-31 17:27:27
合計ジャッジ時間 3,143 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    lines = []
    idx = 1
    for _ in range(N):
        a = int(data[idx])
        b = int(data[idx + 1])
        lines.append((a, b))
        idx += 2

    # Handle the case where all lines are of the form 0 0
    all_zero_b = True
    for a, b in lines:
        if b != 0:
            all_zero_b = False
            break
    if all_zero_b:
        a_values = [a for a, b in lines]
        max_a = max(a_values)
        min_a = min(a_values)
        print(1)
        return

    # Upper envelope processing
    upper_group = {}
    for a, b in lines:
        if b not in upper_group or a > upper_group[b]:
            upper_group[b] = a
    upper_lines = sorted(upper_group.items(), key=lambda x: x[0])
    upper_lines = [(a, b) for b, a in upper_lines]

    deque_upper = deque()
    for a, b in upper_lines:
        if deque_upper:
            # Check if same b as last in deque
            if deque_upper[-1][1] == b:
                if a <= deque_upper[-1][0]:
                    continue
                else:
                    deque_upper.pop()
        while len(deque_upper) >= 2:
            a1, b1 = deque_upper[-2]
            a2, b2 = deque_upper[-1]
            x1 = (a1 - a2) / (b2 - b1)
            a3, b3 = a, b
            if b3 - b2 == 0:
                break
            x2 = (a2 - a3) / (b3 - b2)
            if x1 >= x2:
                deque_upper.pop()
            else:
                break
        deque_upper.append((a, b))

    upper_break_points = []
    for i in range(len(deque_upper) - 1):
        a1, b1 = deque_upper[i]
        a2, b2 = deque_upper[i + 1]
        x = (a1 - a2) / (b2 - b1)
        upper_break_points.append(x)

    # Lower envelope processing
    lower_group = {}
    for a, b in lines:
        if b not in lower_group or a < lower_group[b]:
            lower_group[b] = a
    lower_lines = sorted(lower_group.items(), key=lambda x: x[0])
    lower_lines = [(a, b) for b, a in lower_lines]

    deque_lower = deque()
    for a, b in lower_lines:
        if deque_lower:
            if deque_lower[-1][1] == b:
                if a >= deque_lower[-1][0]:
                    continue
                else:
                    deque_lower.pop()
        while len(deque_lower) >= 2:
            a1, b1 = deque_lower[-2]
            a2, b2 = deque_lower[-1]
            x1 = (a1 - a2) / (b2 - b1)
            a3, b3 = a, b
            if b3 - b2 == 0:
                break
            x2 = (a2 - a3) / (b3 - b2)
            if x1 >= x2:
                deque_lower.pop()
            else:
                break
        deque_lower.append((a, b))

    lower_break_points = []
    for i in range(len(deque_lower) - 1):
        a1, b1 = deque_lower[i]
        a2, b2 = deque_lower[i + 1]
        x = (a1 - a2) / (b2 - b1)
        lower_break_points.append(x)

    # Collect all candidate x's
    candidates = set()

    for x in upper_break_points + lower_break_points:
        if x < 1:
            continue
        floor_x = int(math.floor(x))
        ceil_x = int(math.ceil(x))
        candidates.add(floor_x)
        candidates.add(ceil_x)
        if x == int(x):
            candidates.add(int(x))

    # Compute x_cross
    if not lines:
        print(1)
        return

    max_b = max(b for a, b in lines)
    max_group = [a for a, b in lines if b == max_b]
    p_a = max(max_group) if max_group else 0

    x_p = 1
    for a, b in lines:
        if b < max_b:
            if a > p_a:
                numerator = a - p_a
                denominator = max_b - b
                if denominator == 0:
                    continue
                curr_x = (numerator + denominator - 1) // denominator
                x_p = max(x_p, curr_x)

    min_b = min(b for a, b in lines)
    min_group = [a for a, b in lines if b == min_b]
    q_a = min(min_group) if min_group else 0

    x_q = 1
    for a, b in lines:
        if b > min_b:
            if a < q_a:
                numerator = q_a - a
                denominator = b - min_b
                curr_x = (numerator + denominator - 1) // denominator
                x_q = max(x_q, curr_x)

    x_cross = max(x_p, x_q)
    candidates.add(1)
    candidates.add(x_cross)
    candidates.add(max(1, x_cross - 1))
    candidates.add(x_cross + 1)

    # Evaluate each candidate
    min_f = float('inf')
    best_x = float('inf')

    for x in sorted(candidates):
        if x <= 0:
            continue
        current = []
        for a, b in lines:
            current.append(a + b * x)
        current_max = max(current)
        current_min = min(current)
        f = current_max - current_min
        if f < min_f or (f == min_f and x < best_x):
            min_f = f
            best_x = x

    print(best_x)

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