問題概要
問題ページ
-
-
F - Silver Woods
問題ページへ移動する
問題文
\(xy\) 平面上に \(2\) 直線 \(y=-100,\ y=100\) で囲まれた通路があります。
この通路の中の \(-100 < x < 100\) の部分に \(N\) 本の大きさの無視できる釘が打たれており、 \(i\) 本目の釘の座標は \((x_i, y_i)\) です。
高橋くんは実数 \(r \ (0 < r \leq 100)\) を \(1\) つ選び、半径 \(r\) の円を中心が \((-10^9, 0)\) に位置するように置きます。
その後、円を \((-10^9, 0)\) から \((10^9, 0)\) まで移動させます。
このとき、円は通路の境界や釘が円の内部に入らないような範囲で連続的に動かすことができるものとします。
円を \((10^9, 0)\) まで動かせるような最大の \(r\) を求めてください。
制約
- 入力はすべて整数
- \(1 \leq N \leq 100\)
- \(|x_i|, |y_i| < 100\)
- \(i \neq j\) ならば \((x_i, y_i) \neq (x_j, y_j)\)
問題の考察
ACコード
import sys
class AlgUnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x):
return -self.parents[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
return len(self.roots())
def all_group_members(self):
return {r: self.members(r) for r in self.roots()}
def __str__(self):
return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input().rstrip('\n'))
xy = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
top = n
bot = n + 1
d_l = []
for i in range(n):
for j in range(i + 1, n):
dist = ((xy[i][0] - xy[j][0]) ** 2 + (xy[i][1] - xy[j][1]) ** 2) ** 0.5
d_l.append([dist, i, j])
dist_t = ((xy[i][1] - 100) ** 2) ** 0.5
d_l.append([dist_t, i, top])
dist_b = ((xy[i][1] + 100) ** 2) ** 0.5
d_l.append([dist_b, i, bot])
d_l.sort()
uf = AlgUnionFind(n + 2)
for dist, i, j in d_l:
uf.union(i, j)
if uf.same(top, bot):
print(dist / 2)
exit()
if __name__ == '__main__':
solve()