結果

問題 No.168 ものさし
ユーザー nebukuro09nebukuro09
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 302 ms
81,084 KB
testcase_01 WA -
testcase_02 AC 71 ms
75,820 KB
testcase_03 AC 72 ms
75,668 KB
testcase_04 AC 73 ms
75,680 KB
testcase_05 AC 71 ms
75,520 KB
testcase_06 AC 88 ms
77,952 KB
testcase_07 AC 72 ms
75,660 KB
testcase_08 AC 72 ms
75,520 KB
testcase_09 AC 144 ms
79,360 KB
testcase_10 AC 197 ms
78,976 KB
testcase_11 AC 642 ms
80,896 KB
testcase_12 AC 1,972 ms
85,524 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 AC 74 ms
76,288 KB
testcase_16 AC 125 ms
78,464 KB
testcase_17 AC 143 ms
79,104 KB
testcase_18 AC 174 ms
79,360 KB
testcase_19 AC 767 ms
87,168 KB
testcase_20 AC 783 ms
87,424 KB
testcase_21 AC 824 ms
87,216 KB
testcase_22 AC 805 ms
87,360 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