題目：給出一些螞蟻的點，給出一些樹的點，兩兩對應，使他們的連線不相交，輸出一種方案。
可以任意假定一種組合，然後兩兩判斷，如果相交，則交換，直到全部不相交為止。
這種思想很新穎，被稱為計算幾何中的調整思想。
[cpp]
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<cassert>
#define LL long long
#define eps 1e-8
#define inf 10000
#define zero(a) fabs(a)<eps
#define N 20005
using namespace std;
struct Point{
double x,y;
}ant[105],tree[105];
double xmul(Point p0,Point p1,Point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
bool SegmentAcross(Point s1a,Point s1b,Point s2a,Point s2b){
if(max(s1a.x,s1b.x)>=min(s2a.x,s2b.x)&&max(s2a.x,s2b.x)>=min(s1a.x,s1b.x)
&&max(s1a.y,s1b.y)>=min(s2a.y,s2b.y)&&max(s2a.y,s2b.y)>=min(s1a.y,s1b.y))
if(xmul(s1a,s1b,s2a)*xmul(s1a,s1b,s2b)<-eps)
if(xmul(s2a,s2b,s1a)*xmul(s2a,s2b,s1b)<-eps)
return true;
return false;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%lf%lf",&ant[i].x,&ant[i].y);
for(int i=0;i<n;i++)
scanf("%lf%lf",&tree[i].x,&tree[i].y);
int match[105];
for(int i=0;i<n;i++)
match[i]=i;
while(1){
bool ok=true;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(i==j) continue;
if(SegmentAcross(ant[i],tree[match[i]],ant[j],tree[match[j]])){
swap(match[i],match[j]);
ok=false;
}
}
if(ok) break;
}
for(int i=0;i<n;i++) printf("%d\n",match[i]+1);
}
return 0;
}
還有種做法就是利用KM最小權匹配。
其中的原因便是，最小權的匹配肯定是不相交的。
如果AB與CD相交於E，那麼AC<AE+EC 且BD<BE+ED,那麼AB,CD肯定不是其最小匹配
但是我寫的不知道為什麼TLE，KM不熟，也許有問題，至少可以這麼做，一般在200ms以內
[cpp]
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<cassert>
#define LL long long
#define eps 1e-5
#define inf 1ll<<50
#define zero(a) fabs(a)<eps
#define N 20005
using namespace std;
struct Point{
double x,y;
}ant[105],tree[105];
double path[101][101];
int cnt;
double lx[101],ly[101];
int match[101];
double slack;
bool v_x[101],v_y[101];
double dist(Point p1,Point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool dfs(int k){
v_x[k]=true;
double temp;
for(int i=0;i<cnt;i++){
if(!v_y[i]){
temp=lx[k]+ly[i]-path[k][i];
if(zero(temp)){
v_y[i]=true;
if (match[i]==-1||dfs(match[i])){
match[i]=k;
return true;
}
}
else
slack = max(temp, slack);
}
}
return false;
}
void km(){
for(int i=0;i<cnt;i++){
lx[i]=inf;
ly[i]=0;
for(int j=0;j<cnt;j++)
lx[i]=min(path[i][j],lx[i]);
}
memset(match,-1,sizeof(match));
for(int i=0;i<cnt;i++){
while(1){
memset(v_x,false,sizeof(v_x));
memset(v_y,false,sizeof(v_y));
slack=-inf;
if(dfs(i))
break;
for (int j=0;j<cnt;j++) {
if (v_x[j]) lx[j] -= slack;
if (v_y[j]) ly[j] += slack;
}
}
}
}
int main(){
while(scanf("%d",&cnt)!=EOF){
for(int i=0;i<cnt;i++)
scanf("%lf%lf",&ant[i].x,&ant[i].y);
for(int i=0;i<cnt;i++)
scanf("%lf%lf",&tree[i].x,&tree[i].y);
memset(path,0,sizeof(path));
for(int i=0;i<cnt;i++)
for(int j=0;j<cnt;j++)
path[i][j]=dist(tree[i],ant[j]);
km();
for(int i=0;i<cnt;i++)
printf("%d\n",match[i]+1);
}
return 0;
}
