Bzoj1069 [scoi2007]最大土地面积

基础题

Posted by yjjr's blog on February 10, 2018

标签:计算几何-旋转卡壳

题目

题目传送门

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

分析

枚举四个点计算的话,复杂度可想而知,而且计算几何的常数比较大

做凸包和旋转卡壳(这个到底怎么读啊)

枚举两个点,连一条对角线

然后在这条对角线上下两块分别做两次旋转卡壳计算出最大的那个三角形面积

然后取最大值就好了

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-6
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=2e3+6;
int n,top;
struct P{double x,y;}p[maxn],s[maxn];
inline P operator-(P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline double operator*(P a,P b){return a.x*b.y-a.y*b.x;}
inline double dis(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline bool operator<(P a,P b){
    double t=(a-p[1])*(b-p[1]);
    if(t==0)return dis(a,p[1])<dis(b,p[1]);else return t<0;
}
void graham(){
    int t=1;
    rep(i,2,n)
        if(p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x))t=i; 
    swap(p[1],p[t]);sort(p+2,p+n+1);
    s[++top]=p[1];s[++top]=p[2];
    rep(i,3,n){
        while(top>1&&((p[i]-s[top-1])*(s[top]-s[top-1]))<=0)top--;
        s[++top]=p[i];
    }
    s[top+1]=p[1];
}
inline double RC(){
	double ans=0;int a,b;
	rep(i,1,top){
		a=i%top+1,b=(i+2)%top+1;
		rep(j,i+2,top){
			while(a%top+1!=j&&(s[j]-s[i])*(s[a+1]-s[i])>(s[j]-s[i])*(s[a]-s[i]))a=a%top+1;
			while(b%top+1!=i&&(s[b+1]-s[i])*(s[j]-s[i])>(s[b]-s[i])*(s[j]-s[i]))b=b%top+1;
			ans=max((s[j]-s[i])*(s[a]-s[i])+(s[b]-s[i])*(s[j]-s[i]),ans);
		}
	}
	return ans;
}
int main()
{
	n=read();
	rep(i,1,n)scanf("%lf%lf",&p[i].x,&p[i].y);
	graham();
	printf("%.3lf\n",RC()/2);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr