「BZOJ1069」[SCOI2007] 最大土地面积
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
0 0
1 0
1 1
0 1
0.5 0.5
Sample Output
1.000
HINT
数据范围 n<=2000, |x|,|y|<=100000
题解
n=2000。。。所以可以枚举一条对角线
然后在两边分别找一个最大面积三角形，旋转卡壳。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<deque> #define inf 2000000000 using namespace std; int n,top; struct P{double x,y;}p[2005],s[2005]; double dis(P a,P b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } P operator-(P a,P b) { P t;t.x=a.x-b.x;t.y=a.y-b.y;return t; } double operator*(P a,P b) { return a.x*b.y-a.y*b.x; } 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]); return t<0; } void graham() { int k=1; for(int i=2;i<=n;i++) if(p[k].y>p[i].y||(p[k].y==p[i].y&&p[k].x>p[i].x)) k=i; swap(p[1],p[k]); sort(p+2,p+n+1); s[++top]=p[1];s[++top]=p[2]; for(int i=3;i<=n;i++) { while(top>1&&(p[i]-s[top-1])*(s[top]-s[top-1])<=0) top--; s[++top]=p[i]; } } double RC() { s[top+1]=p[1]; double ans=0; int a,b; for(int x=1;x<=top;x++) { a=x%top+1;b=(x+2)%top+1; for(int y=x+2;y<=top;y++) { while(a%top+1!=y&&(s[y]-s[x])*(s[a+1]-s[x])>(s[y]-s[x])*(s[a]-s[x])) a=a%top+1; while(b%top+1!=x&&(s[b+1]-s[x])*(s[y]-s[x])>(s[b]-s[x])*(s[y]-s[x])) b=b%top+1; ans=max((s[y]-s[x])*(s[a]-s[x])+(s[b]-s[x])*(s[y]-s[x]),ans); } } return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); graham(); printf("%.3lf",RC()/2); return 0; } |
计数器 9334066
OI 课件=>
OI 课件=>
黄XZ，为什么这里的最大四边形一定有三个点是相邻的？（程序里枚举的对角线都是编号差2的，这不就意味着在对角线有一边的三角形是位移确定的吗）