ACM ICPC 2014 World Finals I번 - 문제 링크
답이 되는 원을 생각해보자. 거기엔 가장 먼 두 점이 있다. 우리는 두 점을 결정해 볼 수 있다.
점 A와 B를 결정했고, 그 둘 사이의 거리는 선분 AB의 길이가 된다. 물론 이 선분의 길이는 주어진 d값보다 작거나 같아야겠다. 점 A를 중심으로 선분 AB의 길이(R)만큼의 반지름을 가지는 원과 점 B를 중심으로 길이 R의 반지름을 가지는 원을 생각해볼 수 있다. 어떤 점들이 이 두 원의 교집합 안에 속한다면, 점 A와 점 B로부터 거리가 R 이하인 것이다. 하지만, 위의 그림에서 볼 수 있듯이 내부의 점들 사이의 거리는 R보다 더 클 수 있다. 따라서 이 점들 중 최소개수의 점들을 제거해서 서로 간의 거리가 모두 R이하가 되도록 해야한다.
여기서 선분 AB를 기준으로 위쪽의 영역을 영역1, 아래쪽의 영역을 영역2라고 하자. 각 영역 안에서는 R보다 큰 거리의 점이 존재할 수 없음을 쉽게 알 수 있다. 만약 존재한다고 가정하면, 선분 AB의 길이보다 더 큰 거리에 있게 됨으로 두 점이 모두 영역 내부에 있다는 가정에 모순이 되기 때문이다.
따라서 각 영역에 속하는 점들을 기준으로 이분 그래프를 구성한 후, 쾨닉의 정리에 의해 Maximum Flow를 돌려서 답을 찾으면 된다. 답은 2(점 A와 점 B) + (영역 1에 속하는 점들의 개수) + (영역 2에 속하는 점들의 개수) - (유량)이 된다. 선분 AB 위에 있는 점들은 영역 1 또는 영역 2 어느 쪽에 포함시키던 상관 없다.
여기서 유량을 구하고, 역추적을 하여 답을 찾는 과정은 min-cut을 찾는 것과 동일하게 하면 된다. 만약 소스 기준으로 BFS를 수행한다고 가정하면, 아직 체크되지 않았고 residual이 양수인 것들을 다 같은 색으로 체크한다. 이 때, 왼쪽 그래프에 존재하면서 체크된 점들과, 오른쪽 그래프(싱크쪽)에 존재하면서 체크되지 않은 점들이 maximum independent set이 된다.
const int MAXN = 105;
int N, D, res;
int x[MAXN], y[MAXN], chk[MAXN];
vector <int> ans;
int main() {
scanf("%d%d", &N, &D);
for (int i = 1; i <= N; i++) scanf("%d%d", &x[i], &y[i]);
res = 1; ans.push_back(1);
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
int dist = (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);
if (dist <= D*D) {
int type = 0; int a, b, c;
if (x[i] == x[j]) type = 0;
else if (y[i] == y[j]) type = 1;
else type = 2, a = y[i] - y[j], b = x[j] - x[i], c = - x[j] * y[i] + y[j] * x[i];
vector <int> s, t;
for (int k = 1; k <= N; k++) {
if (k == i || k == j) continue;
int d1 = (x[i] - x[k])*(x[i] - x[k]) + (y[i] - y[k])*(y[i] - y[k]);
int d2 = (x[k] - x[j])*(x[k] - x[j]) + (y[k] - y[j])*(y[k] - y[j]);
if (d1 <= dist && d2 <= dist) {
if (type == 0) {
if (x[k] < x[i]) s.push_back(k);
else t.push_back(k);
}
if (type == 1) {
if (y[k] < y[i]) s.push_back(k);
else t.push_back(k);
}
if (type == 2) {
if (a*x[k] + b*y[k] + c > 0) s.push_back(k);
else t.push_back(k);
}
}
}
int sn = s.size(), tn = t.size();
NetworkFlow f(sn + tn + 2);
for (int k = 1; k <= sn; k++) f.add_edge(0, k, 1, 0);
for (int k = sn + 1; k <= sn + tn; k++) f.add_edge(k, sn + tn + 1, 1, 0);
for (int k = 0; k < sn; k++) for (int l = 0; l < tn; l++) {
int d = (x[s[k]] - x[t[l]])*(x[s[k]] - x[t[l]]) + (y[s[k]] - y[t[l]])*(y[s[k]] - y[t[l]]);
if (d > dist) f.add_edge(k + 1, sn + l + 1, 1, 0);
}
int flow = f.go(0, sn + tn + 1);
int ret = 2 + sn + tn - flow;
if (ret > res) {
res = ret;
for (int i = 0; i <= sn + tn + 1; i++) chk[i] = 0;
queue <int> Q; Q.push(0);
chk[0] = 1;
while (!Q.empty()) {
int X = Q.front(); Q.pop();
for (int i = 0; i < f.adj[X].size(); i++) {
if (chk[f.adj[X][i].target] == 0 && f.adj[X][i].residual() > 0) {
chk[f.adj[X][i].target] = 1;
Q.push(f.adj[X][i].target);
}
}
}
ans.clear();
ans.push_back(i);
ans.push_back(j);
for (int k = 0; k < sn; k++) if (chk[k + 1]) ans.push_back(s[k]);
for (int k = 0; k < tn; k++) if (!chk[sn + k + 1]) ans.push_back(t[k]);
}
}
}
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (auto &X : ans) printf("%d ", X);
}
댓글