题解 P1452 【Beauty Contest】

2018-04-23 13:59:24


要求点之间最大的距离,则这两个点必定是在凸包上,于是就转化成了求凸包

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct node
{
    int x,y;
}p[50100],s[100100];
int cross(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int dis(node a,node b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp1(node a,node b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(node a,node b)
{
    int k=cross(s[1],a,b);
    if(k>0) return 1;
    else if(k==0 && dis(s[1],a)<=dis(s[1],b)) return 1;
    else return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp1);
    s[1]=p[1];
    sort(p+2,p+n+1,cmp2);
    s[2]=p[2];
    int top=2;
    for(int i=3;i<=n;i++)
    {
        while(cross(s[top-1],s[top],p[i])<=0 && top) top--;
        s[++top]=p[i];
    }
    //求凸包详细解释见博客:凸包
    int ans=0;
    s[++top]=s[1];//把第一个点放最后
    int j=3;
    for(int i=1;i<=top;i++)
    {
        while(cross(s[i],s[i+1],s[j])<cross(s[i],s[i+1],s[j+1])) j=j%top+1;//离当前点和下一个点叉积值最大的即为最远的
        ans=max(ans,max(dis(s[i],s[j]),dis(s[i+1],s[j])));
    }
    cout<<ans;
    return 0;
}