結果

問題 No.168 ものさし
ユーザー nebukuro09nebukuro09
提出日時 2016-09-27 14:03:51
言語 PyPy2
(7.3.15)
結果
WA  
実行時間 -
コード長 1,280 bytes
コンパイル時間 667 ms
コンパイル使用メモリ 77,048 KB
実行使用メモリ 87,996 KB
最終ジャッジ日時 2024-05-01 05:42:22
合計ジャッジ時間 7,239 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 272 ms
81,184 KB
testcase_01 WA -
testcase_02 AC 66 ms
75,648 KB
testcase_03 AC 65 ms
75,392 KB
testcase_04 AC 66 ms
75,568 KB
testcase_05 AC 68 ms
75,264 KB
testcase_06 AC 78 ms
78,080 KB
testcase_07 AC 68 ms
75,456 KB
testcase_08 AC 65 ms
75,392 KB
testcase_09 AC 131 ms
79,012 KB
testcase_10 AC 181 ms
79,104 KB
testcase_11 AC 597 ms
80,768 KB
testcase_12 AC 1,774 ms
85,656 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 AC 68 ms
76,700 KB
testcase_16 AC 114 ms
78,872 KB
testcase_17 AC 147 ms
79,388 KB
testcase_18 AC 161 ms
79,232 KB
testcase_19 AC 727 ms
87,212 KB
testcase_20 AC 765 ms
87,996 KB
testcase_21 AC 786 ms
87,856 KB
testcase_22 AC 794 ms
87,560 KB
権限があれば一括ダウンロードができます

ソースコード

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