ABC181 F - Silver Woods
昨日のABCはEまでの5完！やったぜ！
コンテスト本番中はわからなかったFを復習したのでまとめる．
問題概要
下の図のように， から
の直線に挟まれた通路にいくつか釘（赤い点で表す）が打たれている．
円を
から
まで動かすとき，円の内部に釘や通路の境界が入らないようにしたい．
円の半径の最大値を求めよ．
観察
ある2点，もしくは点と直線の距離より円の直径が大きいと，円が通れない．
解法
全点対間距離と，それぞれの点とそれぞれの直線の距離をすべて求めておく．2点，もしくは点と直線のペアを，その距離でソートしておく．そして，距離が小さい2点，もしくは点と直線から順に，線を結ぶとする．線を結んだ間は，円が通れないとする．の直線と
の直線が繋がってしまうときの2点，もしくは点と直線の距離が，求める円の直径の最大値であり，これの半分が求めたい半径である．
上の直線と下の直線が，繋がっていなければ円が通れる．
繋がってしまうと通れなくなる．このときの下図，緑の線で表される距離が，通れる円の直径の最大値．
線を結ぶ，というのは直線と釘を無向グラフの頂点とみなし，union-findで管理する．上と下の直線が連結になったときの距離が，求める直径の最大値．下のコードでは，ソートを整数で行うほうがいいかも？と思って，距離を二乗で管理している．
コード
class UnionFind:
def __init__(self, N):
self.par = [i for i in range(N)]
self.size = [1 for i in range(N)]
def find(self, x):
if self.par[x] == x:
return x
else:
self.par[x] = self.find(self.par[x])
self.size[x] = self.size[self.par[x]]
return self.par[x]
def same(self, x, y):
return self.find(x) == self.find(y)
def merge(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.size[x] < self.size[y]:
x, y = y, x
self.size[x] += self.size[y]
self.par[y] = x
def get_size(self, x):
return self.size[self.find(x)]
def main():
from math import sqrt
import sys
readline = sys.stdin.buffer.readline
N = int(readline())
X = []
Y = []
for _ in range(N):
x, y = (int(i) for i in readline().split())
X.append(x)
Y.append(y)
# 頂点数 N + 2 釘と直線2本
dist = []
for i in range(N):
for j in range(i+1, N):
d = (X[i] - X[j])**2 + (Y[i] - Y[j])**2
dist.append((d, i*(N+2) + j))
# y = 100 との距離 頂点番号N
d = abs(Y[i] - 100)
dist.append((d**2, i*(N+2) + N))
# y = -100 との距離 頂点番号N+1
d = abs(Y[i] + 100)
dist.append((d**2, i*(N+2) + N + 1))
V = N + 2
dist.sort()
uf = UnionFind(V)
ans = -1
for d, pair in dist:
u, v = pair // V, pair % V
uf.merge(u, v)
if uf.same(N, N + 1):
ans = sqrt(d) / 2
break
print(ans)
if __name__ == '__main__':
main()
tatyamさんの公式解説がきれいにまとまっていたので，整理してみたら新しいこと何も言ってないかも．直径や直径の二乗を二分探索してもいいみたい！
コード
class UnionFind:
def __init__(self, N):
self.par = [i for i in range(N)]
self.size = [1 for i in range(N)]
def find(self, x):
if self.par[x] == x:
return x
else:
self.par[x] = self.find(self.par[x])
self.size[x] = self.size[self.par[x]]
return self.par[x]
def same(self, x, y):
return self.find(x) == self.find(y)
def merge(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.size[x] < self.size[y]:
x, y = y, x
self.size[x] += self.size[y]
self.par[y] = x
def get_size(self, x):
return self.size[self.find(x)]
def is_ok(N, V, dist, L):
uf = UnionFind(V)
for d, pair in dist:
u, v = pair // V, pair % V
if L > d:
uf.merge(u, v)
return not uf.same(N, N + 1)
def binary_search(N, V, dist):
ng = 40000
ok = 1
while abs(ok - ng) > 1:
mid = ng + (ok - ng) // 2
if is_ok(N, V, dist, mid):
ok = mid
else:
ng = mid
return ok
def main():
from math import sqrt
import sys
readline = sys.stdin.buffer.readline
N = int(readline())
X = []
Y = []
for _ in range(N):
x, y = (int(i) for i in readline().split())
X.append(x)
Y.append(y)
# 頂点数 N + 2 釘と直線2本
dist = []
for i in range(N):
for j in range(i+1, N):
d = (X[i] - X[j])**2 + (Y[i] - Y[j])**2
dist.append((d, i*(N+2) + j))
# y = 100 との距離 頂点番号N
d = abs(Y[i] - 100)
dist.append((d**2, i*(N+2) + N))
# y = -100 との距離 頂点番号N+1
d = abs(Y[i] + 100)
dist.append((d**2, i*(N+2) + N + 1))
V = N + 2
dist.sort()
# 直径の二乗を二分探索
ans = sqrt(binary_search(N, V, dist)) / 2
print(ans)
if __name__ == '__main__':
main()
その他，コンテスト終了後のTLで見かけた類題や発想が近い？らしい問題．グラフにいい感じに帰着させられるようになりたい～．
