M_sea

洛谷1452 Beauty Contest
LuoguPOJ分析旋转卡壳板子题。求出凸包后直接上旋转卡壳就行了。代码//It is made by M_sea...
扫描右侧二维码阅读全文
23
2019/01

洛谷1452 Beauty Contest

Luogu

POJ

分析

旋转卡壳板子题。

求出凸包后直接上旋转卡壳就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;
const int INF=0x3f3f3f3f;

int n,top=0;
struct Point { int x,y; } a[N],s[N];
Point operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }

inline int cross(Point a,Point b) {
    return a.x*b.y-b.x*a.y;
}

inline int dis(Point a,Point b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

inline int cmp(Point u,Point v) {
    double A=atan2(u.y-a[1].y,u.x-a[1].x);
    double B=atan2(v.y-a[1].y,v.x-a[1].x);
    if (A!=B) return A<B;
    else return u.x<v.x;
}

inline void Graham() {
    int pos=1;
    for (re int i=2;i<=n;++i)
        if (a[i].y<a[pos].y||(a[i].y==a[pos].y&&a[i].x<a[pos].x)) pos=i;
    swap(a[1],a[pos]); sort(a+2,a+n+1,cmp);
    s[top=1]=a[1];
    for (re int i=2;i<=n;i++) {
        while (top>1&&cross(s[top]-s[top-1],a[i]-s[top])<=0) --top;
        s[++top]=a[i];
    }
    s[top+1]=s[1];
}

inline void GetMax() {
    int ans=0;
    if (top==2) { printf("%d\n",dis(s[1],s[2])); return; }
    for (re int i=1,j=3;i<=top;++i) {
        while (cross(s[j]-s[i],s[i+1]-s[j])>cross(s[j+1]-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])));
    }
    printf("%d\n",ans);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
    Graham(); GetMax();
    return 0;
}
最后修改:2019 年 05 月 26 日 06 : 48 PM

发表评论