BZOJ 1069: [SCOI2007]最大土地面积 [旋转卡壳]

1069: [SCOI2007]最大土地面积

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 2978 Solved: 1173
[Submit][Status][Discuss]

Description

　　在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成
的多边形面积最大。

Input

　　第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。

Output

　　最大的多边形面积，答案精确到小数点后3位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

HINT

数据范围 n<=2000, |x|,|y|<=100000

4边形呵呵

枚举对角线，就是两个三角形啊....并且还是两个点确定的...卡就行了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

typedef long long ll;

const int N=;

const double eps=1e-;

inline int sgn(double x){

    if(abs(x)<eps) return ;

    else return x<?-:;

}

struct Vector{

    double x,y;

    Vector(double a=,double b=):x(a),y(b){}

    bool operator <(const Vector &a)const{

        return sgn(x-a.x)<||(sgn(x-a.x)==&&sgn(y-a.y)<);

    }

};

typedef Vector Point;

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

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

Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}

Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}

bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==&&sgn(a.y-b.y)==;}

double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}

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

double Len(Vector a){return sqrt(Dot(a,a));}

double Len2(Vector a){return Dot(a,a);}

double DisTL(Point p,Point a,Point b){

    Vector v1=p-a,v2=b-a;

    return abs(Cross(v1,v2)/Len(v2));

}

int ConvexHull(Point p[],int n,Point ch[]){

    sort(p+,p++n);

    int m=;

    for(int i=;i<=n;i++){

        while(m>&&sgn(Cross(ch[m]-ch[m-],p[i]-ch[m-]))<=) m--;

        ch[++m]=p[i];

    }

    int k=m;

    for(int i=n-;i>=;i--){

        while(m>k&&sgn(Cross(ch[m]-ch[m-],p[i]-ch[m-]))<=) m--;

        ch[++m]=p[i];

    }

    if(n>) m--;

    return m;

}

double S(Vector a,Vector b){return abs(Cross(a,b));}

double RotatingCalipers(Point p[],int n){

    if(n<) return ;

    if(n==) return abs(Cross(p[]-p[],p[]-p[]))/+abs(Cross(p[]-p[],p[]-p[]))/;

    double ans=;

    p[n+]=p[];

    for(int i=;i<=n-;i++){

        int k=i+,l=(i+)%n+;

        for(int j=i+;j<=n;j++){

            while(k+<j&&sgn(S(p[k]-p[i],p[j]-p[i])-S(p[k+]-p[i],p[j]-p[i]))<) k=k+;

            while(l%n+!=i&&sgn(S(p[l]-p[i],p[j]-p[i])-S(p[l%n+]-p[i],p[j]-p[i]))<) l=l%n+;

            ans=max(ans,S(p[k]-p[i],p[j]-p[i])/+S(p[l]-p[i],p[j]-p[i])/);

        }

    }

    return ans;

}

int n;

Point p[N],ch[N];

int main(int argc, const char * argv[]) {

    scanf("%d",&n);

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

    n=ConvexHull(p,n,ch);

    double ans=RotatingCalipers(ch,n);

    printf("%.3f",ans);

}

巴特西