Luogu-4166 [SCOI2007]最大土地面积

求平面内四边形的最大面积

显然四个端点都应该在凸包上，就先求凸包，然后\(n^2\)枚举四边形对角线，对于一个点\(i\)，顺序枚举\(j\)，同时用旋转卡壳的方法去找离对角线最远的两个点。总时间复杂度\(n^2\)

luogu一遍过，但不知道为什么BZOJ死活TLE...

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4+100;
const double eps=1e-9;
struct Vector{
    double x,y;
    Vector(double a=0,double b=0){
        x=a,y=b;
    }
};
struct Point{
    double x,y;
    Point(double a=0,double b=0){
        x=a,y=b;
    }
}a[maxn],tmp[maxn];
int dcmp(double x){return fabs(x)<eps?0:x>0;}
double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}
bool operator < (Point a,Point b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool operator == (Point a,Point b){return a.x==b.x&&a.y==b.y;}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double len(Vector x){return sqrt(dot(x,x));}
int n,m;
void tb(Point *p,int &n){
    if(n==1) return; 
    sort(p+1,p+n+1);
    tmp[m=1]=p[1];
    for(int i=2;i<=n;i++){
        while(m>1&&dcmp((tmp[m]-tmp[m-1])*(p[i]-tmp[m-1]))<=0)
            m--;
        tmp[++m]=p[i];
    }
    int k=m;
    for(int i=n-1;i>=1;i--){
        while(m>k&&dcmp((tmp[m]-tmp[m-1])*(p[i]-tmp[m-1]))<=0)
            m--;
        tmp[++m]=p[i];
    }
    n=m-1;
    for(int i=1;i<m;i++)
        p[i]=tmp[i];
}
double dists(Point p,Point a,Point b){
    Vector v1=b-a,v2=p-a;
    return fabs(v1*v2/len(v1));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    tb(a,n);
    double ans=0;
    a[n+1]=a[1]; 
    for(int i=1;i<=n;i++){
        int x=(i+2)%n+1,y=i%n+1;
        for(int j=i+2;j<=n;j++){
            while(x%n+1!=i&&dcmp(dists(a[x+1],a[i],a[j])-dists(a[x],a[i],a[j]))>0)
                x=x%n+1;
            while(y%n+1!=j&&dcmp(dists(a[y+1],a[i],a[j])-dists(a[y],a[i],a[j]))>0)
                y=y%n+1;
            double z=fabs((a[j]-a[i])*(a[x]-a[y]))/2;
            ans=max(ans,z);
        }
    }
    printf("%.3lf\n",ans);
    return 0;
}

Luogu-4166 [SCOI2007]最大土地面积

原文：https://www.cnblogs.com/nianheng/p/10004521.html