计算几何模板题

There are n boys. All of them are friends. They live in all over the world. One day, one of them wants to know the farthest distance between two boys. Now, you are given the positions of boys. Two boys may in the same position. Your are required to tell boys the farthest distance. Input The first line is one integer n.(1 ≤ n ≤ 105) Each of next n lines has two integers xi and yi, which means the i-th boy's position. (0 ≤ xi, yi ≤ 1010) There are multiple test cases, please stop when n = 0. Output One line for each test case containing a real number in three decimal places.

#include using namespace std;
using namespace rel_ops;

// typedef long long NUM;
typedef double NUM;
const NUM EPS = 1e-12, MAGIC = 2.71828e18;
// 因为有相对误差判断，所以EPS不要设得太宽

inline NUM sqr(NUM a){return a*a;}
inline NUM cmp(NUM a, NUM b){
    // return a-b; // 坐标为浮点数时，使用下面这行
    return fabs(a-b)>=EPS+fabs(a)*EPS?a-b:0;
}

//--------------------------------------------------------------------//

struct VEC {NUM x,y;} NOVEC = {MAGIC,MAGIC};
struct RAY {VEC u,v;} NORAY = {NOVEC,NOVEC};
struct CIR {VEC u; NUM r;} NOCIR = {NOVEC,MAGIC};

inline NUM sqr(const VEC& a){return sqr(a.x)+sqr(a.y);}
inline double abs(const VEC& a){return sqrt(sqr(a));}
inline NUM cmp(const VEC& a, const VEC& b){
    NUM at=cmp(a.x,b.x);
    return !at?cmp(a.y,b.y):at;
}

inline VEC operator +(const VEC& a, const VEC& b)
    {return (VEC){a.x+b.x,a.y+b.y};}
inline VEC operator -(const VEC& a, const VEC& b)
    {return (VEC){a.x-b.x,a.y-b.y};}
inline NUM operator *(const VEC& a, const VEC& b)
    {return a.x*b.y-a.y*b.x;}
inline NUM operator %(const VEC& a, const VEC& b)
    {return a.x*b.x+a.y*b.y;}
inline VEC operator -(const VEC& a){return (VEC){-a.x,-a.y};}
inline VEC operator ~(const VEC& a){return (VEC){-a.y,+a.x};}
inline VEC operator *(NUM u, const VEC& a){return (VEC){u*a.x,u*a.y};}
inline VEC operator *(const VEC& a, NUM u){return (VEC){a.x*u,a.y*u};}
inline VEC operator /(const VEC& a, NUM u){return (VEC){a.x/u,a.y/u};}
inline VEC operator /(const VEC& a, const VEC& b){return a%b/sqr(b)*b;}
inline bool operator ==(const VEC& a, const VEC& b){return !cmp(a,b);}
inline bool operator <(const VEC& a, const VEC& b){return cmp(a,b)<0;}

//  返回值        cmp_side             cmp_axis
//  ==  0       a和b相互平行    /    a和b相互垂直
//  <= -EPS     a在b的左手侧    /    a和b朝向相反（内角大于90度）
//  >= +EPS     a在b的右手侧    /    a和b朝向相同（内角小于90度）
NUM cmp_side(const VEC& a, const VEC& b){return cmp(a.x*b.y,+a.y*b.x);}
NUM cmp_axis(const VEC& a, const VEC& b){return cmp(a.x*b.x,-a.y*b.y);}

//--------------------------------------------------------------------//

// 求向量a长度缩放至u单位后的新向量，a不能是零向量
// 求向量a绕坐标原点o，逆时针转u度后的新向量
VEC resize(const VEC& a, NUM u){return u/abs(a)*a;}
VEC rotate(const VEC& a, NUM u)
    {return (VEC){cos(u)*a.x-sin(u)*a.y,sin(u)*a.x+cos(u)*a.y};}

// 点在直线上的投影(到直线的最近点)
// 点在圆周上的投影(到圆周的最近点)
VEC project(const VEC& p, const RAY& l){
    return (p-l.u)/(l.v-l.u)+l.u;
}
VEC project(const VEC& p, const CIR& c){
    if(!cmp(p,c.u)) return NOVEC;
    return resize(p-c.u,c.r)+c.u;
}

// 求两直线的交点
// 求直线与圆的交点，交线段的方向与原先直线相同
// 求两圆相交的交点，交线段的方向为圆心a到b连线方向逆指针转90度
// 求直线与凸多边形的交点，交线段的方向与原先直线相同，复杂度O(logn)
VEC intersect(const RAY& a, const RAY& b){
    VEC s=a.u-a.v,t=b.u-b.v;
    NUM at=cmp_side(s,t);
    if(!at) return NOVEC;
    return a.u+(b.u-a.u)*t/at*s;
}
RAY intersect(const RAY& l, const CIR& c){
    VEC s=l.u+(c.u-l.u)/(l.v-l.u);
    NUM at=cmp(c.r*c.r,sqr(s-c.u));
    if(at<0) return NORAY;
    VEC t=resize(l.v-l.u,sqrt(at));
    return (RAY){s-t,s+t};
}
RAY intersect(const CIR& a, const CIR& b){
    NUM l=sqr(b.u-a.u);
    NUM w=(1+(a.r*a.r-b.r*b.r)/l)*0.5;
    NUM e=cmp(a.r*a.r/l,w*w);
    if(e<0) return NORAY;
    VEC t=sqrt(e)*~(b.u-a.u);
    VEC s=a.u+w*(b.u-a.u);
    return (RAY){s-t,s+t};
}

// 判断三点是否共线
// 判断点在直线上的投影点，是否在线段上
// 判断点和线的位置关系，在外侧为0，在直线上为1或2(在线段上时为2)
// 判断点和圆的位置关系，在外侧为0，内部为1，边上为2
// 判断点和任意简单多边形的位置关系，在外侧为0，内部为1，边上为2
// 快速地判断点和凸多边形的位置关系，在外侧为0，内部为1，边上为2
// 判断两条线的位置关系，斜相交为0，垂直为1，平行为2，重合为3
bool collinear(const VEC& a, const VEC& b, const VEC& c){
    return !cmp_side(a-b,b-c);
}
bool seg_range(const VEC& p, const RAY& l){
    return cmp_axis(p-l.u,p-l.v)<=0;
}
int relation(const VEC& p, const RAY& l){
    if(cmp_side(p-l.u,p-l.v)) return 0;
    return cmp_axis(p-l.u,p-l.v)>0?1:2;
}
int relation(const VEC& p, const CIR& c){
    NUM at=cmp(sqr(c.r),sqr(c.u-p));
    return at?at<0?0:1:2;
}
int relation(const VEC& p, const vector& u){
    int n=u.size(),ret=0;
    for(int i=0;i0
        && cmp_side(s,t)>0) ret^=1;
    }
    return ret;
}
int relation_convex(const VEC& p, const vector& u){
    int n=u.size(),l=0,r=n-1,o=cmp_side(u[1]-u[0],u[r]-u[0])<0?-1:1;
    if(relation(p,(RAY){u[0],u[1]})==2
    || relation(p,(RAY){u[0],u[r]})==2) return 2;
    while(l tangent(const CIR& a, const CIR& b){
    NUM o=a.r-b.r,l=sqr(b.u-a.u),e=cmp(l,o*o);
    if(e<0) return make_pair(NORAY,NORAY);
    NUM x=o/sqrt(l),y=sqrt(e/l);
    VEC s=resize(b.u-a.u,1),t=~s;
    RAY ll={a.u+a.r*x*s+a.r*y*t,
            b.u+b.r*x*s+b.r*y*t};
    RAY rr={a.u+a.r*x*s-a.r*y*t,
            b.u+b.r*x*s-b.r*y*t};
    return make_pair(ll,rr);
}

// 由散点集构造一个最小覆盖圆，期望复杂度O(n)
CIR min_covering_circle(vector u){
    random_shuffle(u.begin(),u.end());
    int n=u.size(),i,j,k,z=1%n;
    CIR ret;
    for(ret=make_circle(u[0],u[z]),i=2;i convex_hull(vector u){
    sort(u.begin(),u.end()); // 这两行是排序+去重，如果数据已经有保证
    u.erase(unique(u.begin(),u.end()),u.end()); // 则可省略相应的操作
    if(u.size()<3) return u;
    vector c;
    for(size_t i=0,o=1,m=1;~i;i+=o){
        while(c.size()>m){
            VEC a=c.back()-c[c.size()-2];
            VEC b=c.back()-u[i];
            if(cmp_side(a,b)<0) break; // 改成<=0则保留共线点
            c.pop_back();
        }
        c.push_back(u[i]);
        if(i+1==u.size()) m=c.size(),o=-1; // 条件成立时切换至上凸壳
    }
    c.pop_back();
    return c;
}
//两个点的距离
double ff(VEC a,VEC b)
{
    double l=fabs(a.x-b.x);
    double r=fabs(a.y-b.y);
    return sqrt(l*l+r*r);
}
//叉积
double Cross(VEC A,VEC B,VEC C)
{
    return (B-A)*(C-B);
}
//旋转卡壳
double rr(vector u)
{
    int q=1;
    double ans=0;
    int n=u.size();
    u.push_back(u[0]);
    for(int p=0;pCross(u[p],u[q+1],u[p+1])) q=(q+1)%n;
        ans=max(ans,max(ff(u[p],u[q]),ff(u[p+1],u[q])));
    }
    return ans;
}
int n;
void work()
{
    vector u;
    VEC p;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p.x,&p.y);
        u.push_back(p);
    }
    vector ans;
    ans=convex_hull(u);
    printf("%.3lf\n",rr(ans));
}
int main()
{
    while(1)
    {
        scanf("%d",&n);
        if(n==0) return 0;
        work();
    }
}