转载请注明出处,谢谢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;
}
分享到:
相关推荐
北大POJ初级-计算几何学 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要...当然,我们希望得到的小段越长越好,你的任务是计算能够得到的小段木头的最大长度。
1.计算几何 5 1.1 注意 5 1.2几何公式 6 1.3 多边形 8 1.4多边形切割 11 1.5 浮点函数 12 1.6 面积 18 1.7球面 18 1.8三角形 19 1.9三维几何 22 1.10 凸包 30 1.11 网格 32 1.12 圆 33 1.13 矢量运算求几何模板 35 ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
中文大意: 有n只蚂蚁在木棍上爬行,每只蚂蚁的速度都是每秒1单位长度,现在给出所有蚂蚁初始的位置,但是没有给出蚂蚁的运动方向,如果蚂蚁相遇会掉头反向运动,需要求出所有蚂蚁都·掉下木棍的最短时间和最长时间...
计算几何半平面交,poj2451 一题是模版题,这里的代码可以作为模版使用,速度比较快
poj 2653 计算几何算法初步模板,判断两直线是否相交。
计算几何基本知识以及做题时需要注意的地方 ppt
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码