bzoj1069【SCOI2007】最大土地面积
Description
在某块平面土地上有N个点,你可以选择其中的任意四个点,将这片土地围起来,当然,你希望这四个点围成的多边形面积最大。
Input
第1行一个正整数N,接下来N行,每行2个数x,y,表示该点的横坐标和纵坐标。
Output
最大的多边形面积,答案精确到小数点后3位。
Sample Input
50 0
1 0
1 1
0 1
0.5 0.5
Sample Output
1.000HINT
数据范围 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; }
[t].x))>[t].x))>