ARCTIC (중하, p.450)
문제#

어떻게 풀었나?#
Union-Find(Disjoint Set)과 Binary Search를 이용해 풀었다.
정답 코드#
#include <bits/stdc++.h>
using namespace std;
int n;
double x[101], y[101];
int p[101];
int cnt[101];
inline void Init(int n) {
for(int i=0; i<n; i++) {
p[i] = i;
cnt[i] = 1;
}
}
int Find(int x) {
if(x==p[x]) return p[x];
else return p[x] = Find(p[x]);
}
bool Uni(int x, int y) {
x = Find(x);
y = Find(y);
if(x==y) return false;
if(x>y) swap(x,y);
p[y] = x;
cnt[x] += cnt[y];
return true;
}
inline double Diff(double x, double y) {
double ret = x-y;
if(ret<0) return -ret;
else return ret;
}
double Dist(int i, int j) {
double dx = x[i]-x[j];
double dy = y[i]-y[j];
return sqrt(dx*dx + dy*dy);
}
bool Judge(double d) {
Init(n);
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
if(Dist(i,j) < d + 1e-12) {
if (Uni(i, j)) {
if (cnt[Find(i)] == n) return true;
}
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc; cin >> tc;
while(tc--) {
cin >> n;
for(int i=0; i<n; i++) {
cin >> x[i] >> y[i];
}
double lo=0, hi=2000;
while (Diff(lo,hi)>1e-12) {
double mid = (lo+hi)/2;
if(Judge(mid)) hi=mid;
else lo=mid;
}
printf("%.2lf\n", hi);
}
return 0;
}Comment#
난이도 ‘하’는 정말 PS공부를 한번도 해본 적 없는 사람들 조차 맞출 수 있는 문제라 생각해서 ‘중하’정도로 올렸다. 아직 책 풀이법을 보지 않았는데, Disjoint-Set(Union-Find)을 모른다면 모든 점을 다 이을 수 있는지 확인하는 게 여러모로 귀찮을 것 같았다.
또, double 변수에 대한 이분탐색으로 정수형 변수에 대한 이분탐색과는 좀 다르다. 그렇다고 문제가 어려운건 아니지만, 정말 이런 문제를 처음 접해본 사람이라면 헤맬 수도 있지 않을까 생각했다.
확실히 종만북은 정말 갓책인 것 같다. 보통 하나의 문제에도 최소 3개의 기본적인 PS관련 트릭을 알고 있는지 묻고 있는데, 문제 하나하나가 다 주옥같다는 생각이 든다.
책 풀이법을 보니 그냥 BFS로 Judge()부분을 해결했는데, 크루스칼 최소 스패닝 트리를 언급하는 걸 보니 Union-Find 풀이법도 있다는 걸 말하고 있긴 하다.