国际大学生程序设计竞赛例题_4,1遥远的距离
1,题意:y轴左右两个点集,求它们中点的最远距离.2,解决:
最远距离的两个点必定在所有点的凸包上,点到点的最远距离对应点相关的凸包边到点的最远距离.
先求出凸包点,在依次求出每条凸包边对应的最远点,得到一个ans,遍历所有的边即可得到结果.
3,实现代码:
#include <iostream>#include <cmath>using namespace std;/*PointSet[]：输入的点集ch[]：输出的凸包上的点集，按照逆时针方向排列n：PointSet中的点的数目len：输出的凸包上的点的个数*/struct Point{ double x,y;};//小于0,说明向量p0p1的极角大于p0p2的极角double multiply(Point p1,Point p2,Point p0){ return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));}double dis(Point p1,Point p2){ return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));}void Graham_scan(Point PointSet[],Point ch[],int n,int &len){ int i,j,k=0,top=2; Point tmp; //找到最下且偏左的那个点 for(i=1;i<n;i++) if ((PointSet.y<PointSet.y)||((PointSet.y==PointSet.y)&&(PointSet.x<PointSet.x))) k=i; //将这个点指定为PointSet tmp=PointSet; PointSet=PointSet; PointSet=tmp; //按极角从小到大,距离偏短进行排序 for (i=1;i<n-1;i++) { k=i; for (j=i+1;j<n;j++) if( (multiply(PointSet,PointSet,PointSet)>0) ||((multiply(PointSet,PointSet,PointSet)==0) &&(dis(PointSet,PointSet)<dis(PointSet,PointSet))) ) k=j;//k保存极角最小的那个点,或者相同距离原点最近 tmp=PointSet; PointSet=PointSet; PointSet=tmp; } //第三个点先入栈 ch=PointSet; ch=PointSet; ch=PointSet; //判断与其余所有点的关系 for (i=3;i<n;i++) { //不满足向左转的关系,栈顶元素出栈 while(multiply(PointSet,ch,ch)>=0) top--; //当前点与栈内所有点满足向左关系,因此入栈. ch[++top]=PointSet; } len=top+1;}#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y)//返回值点q到线段p1p2的距离double pointToLine(Point p1,Point p2,Point q){ int flag=1; double k; Point s; if (p1.x==p2.x) {s.x=p1.x;s.y=q.y;flag=0;} if (p1.y==p2.y) {s.x=q.x;s.y=p1.y;flag=0;} if (flag) { k=(p2.y-p1.y)/(p2.x-p1.x); s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1); s.y=k*(s.x-p1.x)+p1.y; } if (MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x)) return sqrt((q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y)); else return MIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y)));}const int maxN=200000;Point PointSet;Point ch;int n;//记录点的个数int len;//记录凸包的点数double ans;//结果//求出两两点之间的最远距离void check(Point p1,Point p2){ if( (p1.x<0)!=(p2.x<0) )//保证p1和p2在不同的点集 { double tmp=dis(p1,p2); if(tmp>ans) ans=tmp; }}int main(){ freopen("4.1.in","r",stdin); cout.setf(ios::fixed); cout.precision(3); int cnt; int numa,numb;//两个点集的大小 cin>>cnt; while(cnt--) { ans=0; n=0; cin>>numa>>numb; while(numa--) cin>>PointSet.x>>PointSet.y,n++; while(numb--) cin>>PointSet.x>>PointSet.y,n++; Graham_scan(PointSet,ch,n,len);//返回凸包点,保存到ch double tmp1,tmp2; int i,j=1; //寻找每个点所在凸包边到点的最远距离 //间接得到点到点的最远距离 for(i=0;i<len;i++) { //距离先增加,后降,拐点就是最远的那个点 while(1) { tmp1=pointToLine(ch,ch[(i+1)%len],ch); tmp2=pointToLine(ch,ch[(i+1)%len],ch[(j+1)%len]); if(tmp1<=tmp2) break; } j=(j+1)%len; check(ch,ch); check(ch,ch); check(ch,ch); check(ch,ch); } cout<<ans<<endl; } return 0;}
页:
[1]