結果

問題 No.168 ものさし
コンテスト
ユーザー cologne
提出日時 2026-02-05 13:24:06
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 1,391 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 440 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 86,736 KB
最終ジャッジ日時 2026-02-05 13:24:12
合計ジャッジ時間 4,785 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from bisect import bisect_left
from math import isqrt, inf
from typing import List, Tuple


def int1(x: str, /): return int(x) - 1


def input(): return sys.stdin.readline().rstrip('\n')


def dbg(*args, **kwargs):
    print(*(repr(arg) for arg in args), *(f'{k}: {repr(v)}' for k, v in kwargs.items()),
          sep='; ', file=sys.stderr, flush=True)


def dx(a, b):
    ax, ay = a
    bx, by = b
    sq = (ax - bx) ** 2 + (ay - by) ** 2
    return 0 if sq == 0 else (isqrt(sq - 1) // 10 + 1) * 10


def main():
    n = int(input())
    xy = [tuple(map(int, input().split())) for _ in range(n)]
    d = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i):
            d[i][j] = d[j][i] = dx(xy[i], xy[j])

    vis = [False] * n
    vis[0] = True
    dis = d[0][:]
    ans = 0
    while True:
        mini = None
        for i in range(n):
            if not vis[i]:
                if mini is None or dis[mini] > dis[i]:
                    mini = i

        ans = max(ans, dis[mini])
        if mini == n - 1:
            return ans

        for i in range(n):
            dis[i] = min(dis[i], d[mini][i])
        vis[mini] = True


def _start():
    ret = main()

    if ret is not None:
        if isinstance(ret, List) or isinstance(ret, Tuple):
            print(*ret)
        else:
            print(ret)


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