国际大学生程序设计竞赛例题_4,1遥远的距离

kmplayer

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[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))            k=i;    //将这个点指定为PointSet[0]    tmp=PointSet[0];    PointSet[0]=PointSet[k];    PointSet[k]=tmp;    //按极角从小到大,距离偏短进行排序    for (i=1;i<n-1;i++)    {        k=i;        for (j=i+1;j<n;j++)            if( (multiply(PointSet[j],PointSet[k],PointSet[0])>0)                ||((multiply(PointSet[j],PointSet[k],PointSet[0])==0)                    &&(dis(PointSet[0],PointSet[j])<dis(PointSet[0],PointSet[k]))) )                k=j;//k保存极角最小的那个点,或者相同距离原点最近        tmp=PointSet[i];        PointSet[i]=PointSet[k];        PointSet[k]=tmp;    }    //第三个点先入栈    ch[0]=PointSet[0];    ch[1]=PointSet[1];    ch[2]=PointSet[2];    //判断与其余所有点的关系    for (i=3;i<n;i++)    {        //不满足向左转的关系,栈顶元素出栈        while(multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;        //当前点与栈内所有点满足向左关系,因此入栈.        ch[++top]=PointSet[i];    }    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[maxN];Point ch[maxN];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[n].x>>PointSet[n].y,n++;        while(numb--) cin>>PointSet[n].x>>PointSet[n].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[i],ch[(i+1)%len],ch[j]);                tmp2=pointToLine(ch[i],ch[(i+1)%len],ch[(j+1)%len]);                if(tmp1<=tmp2) break;            }            j=(j+1)%len;            check(ch[i],ch[j]);            check(ch[i+1],ch[j]);            check(ch[i],ch[j+1]);            check(ch[i+1],ch[j+1]);        }        cout<<ans<<endl;    }    return 0;}