結果

問題 No.180 美しいWhitespace (2)
ユーザー lam6er
提出日時 2025-03-20 20:29:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,822 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 75,404 KB
最終ジャッジ日時 2025-03-20 20:30:30
合計ジャッジ時間 2,722 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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

def build_upper_envelope(processed_lines):
    stack = []
    for line in processed_lines:
        a, b = line
        while len(stack) >= 2:
            a1, b1 = stack[-2]
            a2, b2 = stack[-1]
            numerator_prev = a2 - a1
            denominator_prev = b1 - b2
            numerator_new = a - a2
            denominator_new = b2 - b
            lhs = numerator_new * denominator_prev
            rhs = numerator_prev * denominator_new
            if lhs <= rhs:
                stack.pop()
            else:
                break
        stack.append((a, b))
    return stack

# Process upper envelope
upper_amap = {}
for a, b in lines:
    if b in upper_amap:
        if a > upper_amap[b]:
            upper_amap[b] = a
    else:
        upper_amap[b] = a
ue_items = sorted(upper_amap.items(), key=lambda x: (-x[0], -x[1]))  # sort by b descending, then a descending
ue_processed = [(a, b) for b, a in ue_items]
upper_stack = build_upper_envelope(ue_processed)

# Process lower envelope by converting lines and using the same upper envelope function
lower_amap = {}
for a, b in lines:
    neg_b = -b
    neg_a = -a
    if neg_b in lower_amap:
        if neg_a > lower_amap[neg_b]:
            lower_amap[neg_b] = neg_a
    else:
        lower_amap[neg_b] = neg_a
le_items = sorted(lower_amap.items(), key=lambda x: (-x[0], -x[1]))  # sort by converted b (neg_b) descending
le_processed = [(a, b) for b, a in le_items]
lower_stack = build_upper_envelope(le_processed)

def generate_candidates(stack):
    candidates = set()
    for i in range(len(stack) - 1):
        a1, b1 = stack[i]
        a2, b2 = stack[i+1]
        denominator = b1 - b2
        if denominator == 0:
            continue
        numerator = a2 - a1
        x = numerator / denominator
        if x <= 0:
            continue
        floor_x = math.floor(x)
        ceil_x = math.ceil(x)
        if floor_x > 0:
            candidates.add(floor_x)
        if ceil_x > 0:
            candidates.add(ceil_x)
        if x == int(x):
            candidates.add(int(x))
    return candidates

candidates = set()
candidates.update(generate_candidates(upper_stack))
candidates.update(generate_candidates(lower_stack))
candidates.add(1)

candidates = [x for x in sorted(candidates) if x >= 1]

min_f = None
best_x = 1

for x in candidates:
    current_max = -float('inf')
    current_min = float('inf')
    for a, b in lines:
        s = a + b * x
        if s > current_max:
            current_max = s
        if s < current_min:
            current_min = s
    current_f = current_max - current_min
    if (min_f is None) or (current_f < min_f) or (current_f == min_f and x < best_x):
        min_f = current_f
        best_x = x

print(best_x)
0