POJ 3565 Ants（计算几何，KM） - c++编程基础

题目：给出一些蚂蚁的点，给出一些树的点，两两对应，使他们的连线不相交，输出一种方案。
可以任意假定一种组合，然后两两判断，如果相交，则交换，直到全部不相交为止。
这种思想很新颖，被称为计算几何中的调整思想。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define inf 10000
#define zero(a) fabs(a) #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 scanf("%lf%lf",&ant[i].x,&ant[i].y);
for(int i=0;i scanf("%lf%lf",&tree[i].x,&tree[i].y);
int match[105];
for(int i=0;i match[i]=i;
while(1){
bool ok=true;
for(int i=0;i for(int j=0;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 }
return 0;
}

还有种做法就是利用KM最小权匹配。
其中的原因便是，最小权的匹配肯定是不相交的。
如果AB与CD相交于E，那么AC 但是我写的不知道为什么TLE，KM不熟，也许有问题，至少可以这么做，一般在200ms以内
[cpp]
#include
#include
#include
#include

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-5
#define inf 1ll<<50
#define zero(a) fabs(a) #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 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 lx[i]=inf;
ly[i]=0;
for(int j=0;j lx[i]=min(path[i][j],lx[i]);
}
memset(match,-1,sizeof(match));
for(int i=0;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 if (v_x[j]) lx[j] -= slack;
if (v_y[j]) ly[j] += slack;
}
}
}
}
int main(){
while(scanf("%d",&cnt)

POJ 3565 Ants（计算几何，KM）(一)