結果

問題 No.168 ものさし
ユーザー nebukuro09
提出日時 2016-09-27 14:03:51
言語 PyPy2
(7.3.15)
結果
WA  
実行時間 -
コード長 1,280 bytes
コンパイル時間 2,760 ms
コンパイル使用メモリ 76,800 KB
実行使用メモリ 160,128 KB
最終ジャッジ日時 2024-11-21 07:16:13
合計ジャッジ時間 16,432 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16 WA * 1 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

class UnionFind(object):
    def __init__(self, n):
        self.uf = [-1 for _ in xrange(n)]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.uf[x] >= self.uf[y]:
            self.uf[y] += self.uf[x]
            self.uf[x] = y
        else:
            self.uf[x] += self.uf[y]
            self.uf[y] = x

    def find(self, x):
        leaves = []
        while self.uf[x] >= 0:
            leaves.append(x)
            x = self.uf[x]
        for lf in leaves:
            self.uf[lf] = x
        return x

N = input()
points = [map(int, raw_input().split()) for _ in xrange(N)]
f = lambda p1, p2:(p1[0]-p2[0])**2+(p1[1]-p2[1])**2
dists = [[0 for i in xrange(N)] for j in xrange(N)]
for i in xrange(N):
    for j in xrange(i+1, N):
        dists[i][j] = f(points[i], points[j])

high = 8*10**18
low = 0
while high - low > 1:
    uf = UnionFind(N)
    middle = (high+low)/2
    for i in xrange(N):
        for j in xrange(i+1, N):
            if dists[i][j] <= middle:
                uf.union(i, j)
    if uf.find(0) == uf.find(N-1):
        high = middle
    else:
        low = middle

sqrt = int(math.sqrt(high))
if sqrt**2 != high:
    sqrt += 1
print sqrt/10*10+(sqrt%10>0)*10
0