POJ 3565 Ants（计算几何，KM）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：给出一些蚂蚁的点，给出一些树的点，两两对应，使他们的连线不相交，输出一种方案。

http://poj.org/problem?id=3565

可以任意假定一种组合，然后两两判断，如果相交，则交换，直到全部不相交为止。

这种思想很新颖，被称为计算几何中的调整思想。

#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以内

#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;
}