【BZOJ 1069】 凸包+旋转卡壳

时间：2023-03-08 16:59:57

1069: [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

Sample Output

1.000

HINT

数据范围 n<=2000, |x|,|y|<=100000

【分析】

　　这个叫旋转 qia 壳？

　　好吧，去偷个gif回来。。

　　【BZOJ 1069】 凸包+旋转卡壳

　　其实还是形象生动，旋转卡壳是算点到线段的距离的，就是两条线扫啊扫，有点单调的意思。

　　这题里，枚举四边形的对角线，然后两边找离这条线段的最远的点，可以证明这些点都是在凸包上的（好像很明显??）

　　就直接在凸包上找，假设已经枚举了线段x-y，现在枚举x-y+1，卡壳线不断逆时针旋转就可以了（我的打法是逆时针旋转），因为前面去掉的点以后肯定也没有用的，嗯。。

　　然后，这里要用到平面差积，差积的值是有正负的，所以用差积算面积的时候要小心一点。然后也是用差积比较斜率的。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 #define Maxn 2010

 int n;

 const double eps=0.000001;

 struct P{double x,y;}a[Maxn],c[Maxn];

 int len;

 double mymax(double x,double y) {return x>y?x:y;}

 double myabs(double x) {return x<?-x:x;}

 P operator - (P x,P y)

 {

     P tt;

     tt.x=x.x-y.x;tt.y=x.y-y.y;

     return tt;

 }

 int dcmp(double x)

 {

     if(myabs(x)<eps) return ;

    else return x<?-:;

 }

 bool cmp(P x,P y) {return dcmp(x.x-y.x)==?(x.y<y.y):(x.x<y.x);}

 double Dot(P x,P y) {return x.x*y.x+x.y*y.y;}

 double Cross(P x,P y) {return x.x*y.y-x.y*y.x;}

 void chull()

 {

     sort(a+,a++n,cmp);

     len=;

     for(int i=;i<=n;i++)

     {

         while(len>&&Cross(c[len]-c[len-],a[i]-c[len])<=) len--;

         c[++len]=a[i];

     }

     int k=len;

     for(int i=n-;i>=;i--)

     {

         while(len>k&&Cross(c[len]-c[len-],a[i]-c[len])<=) len--;

         c[++len]=a[i];

     }

     len--;

 }

 double ans=;

 void RC()//rotating calipers

 {

     for(int i=;i<=len;i++)

     {

         int k1=i%len+,k2=(i+)%len+;//两边一起做旋转卡壳

         for(int j=i+;j<=len;j++)

         {

             while(k1%len+!=j&&Cross(c[k1+]-c[i],c[j]-c[i])>Cross(c[k1]-c[i],c[j]-c[i]))

                 k1=k1%len+;

             while(k2%len+!=i&&Cross(c[j]-c[i],c[k2+]-c[i])>Cross(c[j]-c[i],c[k2]-c[i]))

                 k2=k2%len+;

             ans=mymax(ans,Cross(c[j]-c[i],c[k2]-c[i])+Cross(c[k1]-c[i],c[j]-c[i]));

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

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

     }

     chull();

     RC();

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

     return ;

 }

2016-12-10 09:44:52

有一篇很好的讲旋转卡壳的博：

http://blog.****.net/hanchengxi/article/details/8639476

相关文章