P1452 Beauty Contest

题意

求平面\(n(\le 50000)\)个点的最远点对

收获了一堆计算几何的卡点..

凸包如果不保留共线的点，在加入上凸壳时搞一个相对栈顶，以免把\(n\)号点删走了

旋转卡壳和凸包都想一下更新的时候带不带等于号阿

Code:

#include <cstdio>

#include <algorithm>

using std::max;

const int N=5e4+10;

int s[N],tot,n,p;

struct Vector

{

    int x,y;

    bool friend operator <(Vector a,Vector b){return a.x==b.x?a.y<b.y:a.x<b.x;}

    Vector friend operator -(Vector a,Vector b){return Vector{a.x-b.x,a.y-b.y};}

}bee[N];

int Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}

int cal(int a,int b,int c){return Cross(bee[c]-bee[a],bee[c]-bee[b]);}

int Dis(int a,int b){return (bee[a].x-bee[b].x)*(bee[a].x-bee[b].x)+(bee[a].y-bee[b].y)*(bee[a].y-bee[b].y);}

void ins(int i)

{

    while(tot>p&&Cross(bee[i]-bee[s[tot]],bee[s[tot]]-bee[s[tot-1]])>=0) --tot;

    s[++tot]=i;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d%d",&bee[i].x,&bee[i].y);

    std::sort(bee+1,bee+1+n);

    int ans=Dis(1,n);p=1;

    for(int i=1;i<=n;i++) ins(i);

    p=tot;

    for(int i=n-1;i;i--) ins(i);

    for(int p=2,i=1;i<tot;i++)

    {

        while(cal(s[i],s[i+1],s[p])<cal(s[i],s[i+1],s[p+1])) p=p==tot-1?1:p+1;

        ans=max(ans,max(Dis(s[i],s[p]),Dis(s[i+1],s[p])));

    }

    printf("%d\n",ans);

    return 0;

}

2019.2.15

巴特西

洛谷 P1452 Beauty Contest 解题报告

P1452 Beauty Contest

题意

最新文章

热门文章