luogu P4166 [SCOI2007]最大土地面积 凸包 旋转卡壳

时间：2023-03-09 19:47:34
luogu P4166 [SCOI2007]最大土地面积 凸包 旋转卡壳

LINK：最大土地面积

容易想到四边形的边在凸包上面 考虑暴力枚举凸包上的四个点计算面积。

不过可以想到可以直接枚举对角线的两个点找到再在两边各找一个点 这样复杂度为\(n^3\)

可以得到50分。

考虑继续优化 观察 那个点可以三分做 所以复杂度为\(n^2log\)

最后可以模拟旋转卡壳的过程 枚举两个点i和j的时候 随着j的增大那么之前的点单调递增 所以可以单调的增加 这样就不需要枚举第三个点了。

复杂度\(n^2\)

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 1000000000000000000ll

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007

#define F first

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define ull unsigned long long

#define ui unsigned

#define EPS 1e-5

#define sq sqrt

#define mod 998244353

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

    RE int x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}

    return x*f;

}

const int MAXN=2010;

struct Vec

{

	db x,y;Vec(){}Vec(db a,db b){x=a;y=b;}

	inline Vec operator +(Vec b){return Vec(x+b.x,y+b.y);}

	inline Vec operator -(Vec b){return Vec(x-b.x,y-b.y);}

	inline db operator *(Vec b){return x*b.x+y*b.y;}

	inline db operator %(Vec b){return x*b.y-b.x*y;}

	inline db operator ~(){return x*x+y*y;}

	inline bool operator ==(Vec b){return fabs(x-b.x)<=EPS&&fabs(y-b.y)<=EPS;}

	inline bool operator !=(Vec b){return fabs(x-b.x)>EPS||fabs(y-b.y)>EPS;}

	inline bool operator <(Vec b){return fabs(y-b.y)<=EPS?x<b.x:y<b.y;}

};typedef Vec pt;

inline Vec operator /(Vec a,db k){return Vec(a.x/k,a.y/k);}

inline Vec operator *(db k,Vec a){return Vec(a.x*k,a.y*k);}

inline Vec operator *(Vec a,db k){return Vec(a.x*k,a.y*k);}

inline bool para(Vec a,Vec b){return fabs(a%b)<=EPS;}

inline bool Toleft(Vec a,Vec b){return b%a>EPS;}

int n,top;int nex[MAXN],pre[MAXN];

pt a[MAXN],s[MAXN],LTL;

inline bool cmpltl(pt a,pt b){return para(a=a-LTL,b=b-LTL)?~a<~b:Toleft(b,a);}

int main()

{

	freopen("1.in","r",stdin);

	gt(n);

	rep(1,n,i)scanf("%lf%lf",&a[i].x,&a[i].y);

	LTL=*min_element(a+1,a+1+n);

	sort(a+1,a+1+n,cmpltl);

	rep(1,n,i)

	{

		while(top>1&&!Toleft(a[i]-s[top-1],s[top]-s[top-1]))--top;

		s[++top]=a[i];

	}

	db ans=0;

	rep(1,top,i)nex[i]=i+1,pre[i]=i-1;nex[top]=1;pre[1]=top;

	rep(1,top,i)

	{

		int j=nex[nex[i]];

		int a=nex[i];

		int b=nex[j];

		while(j!=pre[i])

		{

			while((s[nex[a]]-s[i])%(s[j]-s[i])>(s[a]-s[i])%(s[j]-s[i]))a=nex[a];

			while((s[j]-s[i])%(s[nex[b]]-s[i])>(s[j]-s[i])%(s[b]-s[i]))b=nex[b];

			ans=max(ans,(s[j]-s[i])%(s[b]-s[i])+(s[a]-s[i])%(s[j]-s[i]));

			j=nex[j];

		}

	}

	printf("%.3lf",ans/2);

	return 0;

}

相关文章