結果

問題 No.180 美しいWhitespace (2)
ユーザー lam6er
提出日時 2025-04-15 23:57:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,799 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 81,404 KB
実行使用メモリ 158,208 KB
最終ジャッジ日時 2025-04-15 23:58:41
合計ジャッジ時間 10,100 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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

candidates = set()
candidates.add(1)  # x=1 is always a candidate

for i in range(n):
    a_i, b_i = lines[i]
    for j in range(i + 1, n):
        a_j, b_j = lines[j]
        if b_i == b_j:
            continue  # same slope, no intersection
        denominator = b_i - b_j
        numerator = a_j - a_i
        if denominator == 0:
            continue  # avoid division by zero (though logically impossible here)
        x = numerator / denominator
        if x <= 0:
            continue  # only consider positive x
        if x.is_integer():
            x_int = int(x)
            candidates.add(x_int)
        else:
            x_floor = math.floor(x)
            x_ceil = x_floor + 1
            candidates.add(x_floor)
            candidates.add(x_ceil)

# Convert to list and filter positive integers
candidates = [x for x in candidates if x > 0]
candidates.append(1)  # Ensure x=1 is included even if no candidates were found
candidates = sorted(list(set(candidates)))  # Remove duplicates and sort

min_f = float('inf')
best_x = 1  # default to x=1

for x in candidates:
    current = []
    for a, b in lines:
        current_val = a + b * x
        current.append(current_val)
    max_val = max(current)
    min_val = min(current)
    f = max_val - min_val
    if f < min_f or (f == min_f and x < best_x):
        min_f = f
        best_x = x

# Check if all b_i are the same (special case)
b_values = [b for a, b in lines]
max_b = max(b_values)
min_b = min(b_values)
if max_b == min_b:
    a_values = [a for a, b in lines]
    current_f = max(a_values) - min(a_values)
    if current_f < min_f or (current_f == min_f and 1 < best_x):
        best_x = 1
        min_f = current_f

print(best_x)
0