【bzoj1069】[SCOI2007]最大土地面积

2015.06.24 14:57 Wed | 26次阅读 | 旧日oi | 固定链接 | 源码

题目大意,给定一些点,选出4个点,使其围成的面积最大。
题解
旋转卡壳模板

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 4005
struct Point
{
    double x,y;
    Point(double _,double __):x(_),y(__){}
    Point(){}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a)const{
        return Point(x-a.x,y-a.y);
    }
    Point operator *(double a)const{
        return Point(x*a,y*a);
    }
    double operator *(const Point &a)const{
        return x*a.y-y*a.x;
    }
    Point operator /(double a)const{
        return Point(x/a,y/a);
    }
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
}p[N],st[N];
int n,top;
bool cmp1(const Point &a,const Point &b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
double dis(const Point &a)
{
    return sqrt(a.x*a.x+a.y*a.y);
}
bool cmp2(const Point &a,const Point &b)
{
    double k=(a-p[1])*(b-p[1]);
    if(k==0) return dis(a-p[1])>dis(b-p[1]);
    return k>0;
}
void convex_hull()
{
    sort(p+1,p+n+1,cmp1);
    sort(p+2,p+n+1,cmp2);
    st[1]=p[1];st[2]=p[2];st[3]=p[3];top=3;
    for(int i=4;i<=n;i++)
    {
        while(top>=3&&(st[top]-st[top-1])*(p[i]-st[top-1])<=0) top--;
        st[++top]=p[i];
    }
}
double ans;
void xzqk()
{
    for(int i=1;i<=top;i++) st[top+i]=st[i];
    for(int p1,p2,p3,i=1;i<=top;i++)
    {
        p1=i+1;p2=i+2;p3=i+3;
        for(;p2<i+top-1;p2++)
        {
            while(p1<p2-1)
            {
                if(fabs((st[p1]-st[i])*(st[p2]-st[i]))<fabs((st[p1+1]-st[i])*(st[p2]-st[i]))) p1++;
                else break;
            }
            while(p3<i+top)
            {
                if(fabs((st[p3]-st[i])*(st[p2]-st[i]))<fabs((st[p3+1]-st[i])*(st[p2]-st[i]))) p3++;
                else break;
            }
            if(p3!=i+top)
                ans=max(ans,fabs((st[p1]-st[i])*(st[p2]-st[i]))+fabs((st[p3]-st[i])*(st[p2]-st[i])));
        }
    }
    printf("%.3lf\n",ans/2);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) p[i].read();
    convex_hull();
    xzqk();
}```