看大家都是二分图匹配或费用流,我来发个分治做法的吧。
算法
分治
时间复杂度
$O(nlog(n))$
C++ 代码
#include<bits/stdc++.h>
#define bug printf("!!!\n")
using namespace std;
const int maxn = 5000;
int n;
int match[maxn];
struct node{
int x, y, op, id;
double theta;
}nodes[maxn];
void cal(int flag, int i){
double x = nodes[i].x - nodes[flag].x, y = nodes[i].y - nodes[flag].y;
double theta = atan2(y, x);
nodes[i].theta = theta;
}
bool cmp(node x, node y){
return x.theta < y.theta;
}
void solve(int l, int r){
if(r <= l) return;
int minx = nodes[l].x, flag = l;
for(int i = l; i <= r; i++){
if(nodes[i].x < minx){
minx = nodes[i].x;
flag = i;
}
}
for(int i = l; i <= r; i++){
if(i == flag){
nodes[i].theta = 180;
continue;
}
cal(flag, i);
}
sort(nodes + l, nodes + r + 1, cmp);
flag = r;
int cnt = 0, op = 3 - nodes[flag].op;
for(int i = l; i <= r; i++){
if(cnt == 0 && nodes[i].op == op){
if(op == 1) {
match[nodes[i].id] = nodes[flag].id;
}
else {
match[nodes[flag].id] = nodes[i].id;
}
solve(l, i - 1);
solve(i + 1, r - 1);
return;
}
if(nodes[i].op==1) cnt++;
else cnt--;
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d%d", &nodes[i].x, &nodes[i].y);
nodes[i].id = i;
nodes[i].op = 1;
}
for(int i = n + 1; i <= 2 * n; i++){
scanf("%d%d", &nodes[i].x, &nodes[i].y);
nodes[i].id = i - n;
nodes[i].op = 2;
}
solve(1, 2 * n);
for(int i = 1; i <= n; i++)
printf("%d\n", match[i]);
}
这个最坏是 $\mathcal O(n^2\log n)$ 的吧
而且最好情况下也是 $\mathcal O(n\log^2 n)$ 的