M_sea

洛谷4166 [SCOI2007]最大土地面积
LuoguBZOJ分析显然选的点要在凸包上。于是先求出凸包。然后,旋转卡壳确定一条对角线,然后$O(n)$扫描,找...
扫描右侧二维码阅读全文
27
2019/01

洛谷4166 [SCOI2007]最大土地面积

Luogu

BZOJ

分析

显然选的点要在凸包上。于是先求出凸包。

然后,旋转卡壳确定一条对角线,然后$O(n)$扫描,找到对角线左右两个面积最大的三角形,合起来就是四边形的面积。

总时间复杂度$O(n^2)$。

代码

#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=2000+10;
const int INF=0x3f3f3f3f;

struct Point { double x,y; };
typedef Point Vector;
Vector operator -(const Point a,const Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n,top=0;
Point a[N],s[N];

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 double calc(int x,int y) {
    double ans=0,tmp=0;
    for (re int i=x;i!=y;i=i%top+1)
        tmp=max(tmp,fabs(cross(s[i]-s[x],s[i]-s[y])/2));
    ans+=tmp,tmp=0;
    for (re int i=y;i!=x;i=i%top+1)
        tmp=max(tmp,fabs(cross(s[i]-s[x],s[i]-s[y])/2));
    ans+=tmp; return ans;
}

inline void Solve() {
    double ans=0;
    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,calc(i,j)),ans=max(ans,calc(i%top+1,j));
    }
    printf("%.3f\n",ans);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
    Graham();
    Solve();
    return 0;
}
最后修改:2019 年 05 月 26 日 07 : 58 PM

4 条评论

  1. Ivystorm

    %%%julao

  2. smy

    计算几何聚聚%%%

    1. M_sea
      @smy

      您早就会了啊...

      1. smy
        @M_sea

        但还是被您吊打啊

发表评论