Bakser's Blog

我是逗比。

bzoj1069 计算几何

| Comments

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double ld;
#define MAX(a,b) (((a)>(b))?(a):(b))
const ld eps(1e-8);
#define N 10010
ld ans;
template<class T>
T abs(T a)
{
    return a>0?a:(-a);
}
struct hh
{
    ld x,y;
    hh(ld _x=0,ld _y=0):x(_x),y(_y){}
}p[N],s[N];
int n,top,tot;
inline int cmp(ld x)
{
    if(x>eps)return 1;
    else if(x<-eps)return -1;
    return 0;
}
bool operator<(const hh &a,const hh &b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
inline ld add(ld a,ld b)
{
    if(abs(a+b)<eps*(abs(a)+abs(b)))return 0;
    return a+b;
}
inline hh operator -(const hh &a,const hh &b)
{
    return hh(add(a.x,-b.x),add(a.y,-b.y));
}
inline ld cross(const hh &a,const hh &b)
{
    return add(a.x*b.y,-b.x*a.y);
}
inline ld det(const hh &o,const hh &a,const hh &b)
{
    return cross(a-o,b-o);
}
inline ld area(const hh &a,const hh &b,const hh &c,const hh &d)
{
    return cross(b-a,d-c);
}
inline void graham_scan()
{
    sort(p,p+n);
    top=0;
    for(int i=0;i<n;i++)
    {
        while(top>=2&&cross(s[top-1]-s[top-2],p[i]-s[top-2])<=0)top--;
        s[top++]=p[i];
    }
    int tmp=top+1;
    for(int i=n-2;i>=0;i--)
    {
        while(top>=tmp&&cross(s[top-1]-s[top-2],p[i]-s[top-2])<=0)top--;
        s[top++]=p[i];
    }
    top--;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        double tx,ty;
        scanf("%lf%lf",&tx,&ty);
        p[i].x=(ld)tx;p[i].y=(ld)ty;
    }
    graham_scan();
    for(int i=0;i<top;i++)s[top+i]=s[i];
    for(int i=0;i<top;i++)
    {
        int l=i+1,r=i+3;
        for(int j=i+2;j<i+top;j++)
        {
            while(cmp(area(s[i],s[j],s[l],s[l+1]))<0)l++;
            while(cmp(area(s[j],s[i],s[r],s[r+1]))<0&&r-i<top)r++;
            ans=MAX(ans,(abs(det(s[i],s[l],s[j]))+abs(det(s[i],s[j],s[r])))/2.0);
        }
    }        
    printf("%.3f\n",(double)ans);
    return 0;
}

Comments

comments powered by Disqus