当前位置： 移动技术网 > IT编程>开发语言>C/C++ > bzoj1069【SCOI2007】最大土地面积

bzoj1069【SCOI2007】最大土地面积

2018年03月31日  | 移动技术网IT编程  | 我要评论

谢云汉,秒杀聚划算,龙极纹身

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

很显然这四个点都是凸包上的。

枚举对角线，然后维护一下另外两个顶点，发现另外两个顶点是单调的，用旋转卡壳的思想很好实现。


#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 2005
#define eps 1e-8
using namespace std;
int n,top;
double ans;
struct data{double x,y;}p[maxn],s[maxn];
inline double dcmp(double a)
{
	if (fabs(a)<=eps) return 0;
	else return a>0?1:-1;
}
inline double dis(data a,data b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline data operator -(data a,data b)
{
	return (data){a.x-b.x,a.y-b.y};
}
inline double operator *(data a,data b)
{
	return a.x*b.y-a.y*b.x;
}
inline bool operator <(data a,data b)
{
	int t=dcmp((p[1]-a)*(p[1]-b));
	if (t==0) return dis(p[1],a)0;
}
inline void solve()
{
	int t=1;
	F(i,2,n) if (p[i].y1&&dcmp((p[i]-s[top-1])*(s[top]-s[top-1]))>=0) top--;
		s[++top]=p[i];
	}
}
inline void getans()
{
	int a,b;
	s[top+1]=s[1];
	F(x,1,top-2)
	{
		a=x%top+1;b=(x+2)%top+1;
		F(y,x+2,top)
		{
			while (a%top+1!=y&&dcmp((s[a+1]-s[x])*(s[y]-s[x])-(s[a]-s[x])*(s[y]-s[x]))>0) a=a%top+1;
			while (b%top+1!=x&&dcmp((s[y]-s[x])*(s[b+1]-s[x])-(s[y]-s[x])*(s[b]-s[x]))>0) b=b%top+1;
			ans=max(ans,(s[a]-s[x])*(s[y]-s[x])+(s[y]-s[x])*(s[b]-s[x]));
		}
	}
}
int main()
{
	scanf("%d",&n);
	F(i,1,n) scanf("%lf%lf",&p[i].x,&p[i].y);
	solve();
	getans();
	printf("%.3lf\n",ans/2.0);
	return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网