BZOJ 1069 [SCOI2007]最大土地面积 旋转卡壳

题意:链接方法:旋转卡壳解析:跟POJ2079那个三角形的很像。所以思路其实也是一个思路。但是注意到本题是找四边形，如果找三个动点的话好像不太现实。所以我们枚举对角线的话，对角线上下肯定各有一个点，而且发现下面的点逆时针转动的时候，上面的点其实也是逆时针走。所以按照旋转卡壳的思想，，我们需要枚举一下对角线，再找两个动点更新最大即可。这个复杂度是O(n^2)->枚举定点以及其对角点，对于本题来说可过。代码:;int n;struct Point{double x,y;friend istream& operator >> (istream &_,Point &a){scanf(“%lf%lf”,&a.x,&a.y);return _;}Point(){}Point(double a,double b):x(a),y(b){}Point operator + (const Point &a){return Point(x+a.x,y+a.y);}Point operator – (const Point &a){return Point(x-a.x,y-a.y);}Point operator * (double rate){return Point(x*rate,y*rate);}double operator * (const Point &a){return x*a.x+y*a.y;}double operator ^ (const Point &a){return x*a.y-y*a.x;}< (Point a,Point b){if(a.x==b.x)return a.y>b.y;return a.x<b.x;}}pt[N];int sta[N];int staa[N];int top;int topp;double Rotating_Calipers(){double ret=0;for(int i=0;i<topp;i++){int p=1,q=1;for(int j=i+2;j<topp;j++){while(((pt[staa[p+1]]-pt[staa[i]])^(pt[staa[j]]-pt[staa[i]]))>((pt[staa[p]]-pt[staa[i]])^(pt[staa[j]]-pt[staa[i]])))p=(p+1)%topp;while(((pt[staa[j]]-pt[staa[i]])^(pt[staa[q+1]]-pt[staa[i]]))>((pt[staa[j]]-pt[staa[i]])^(pt[staa[q]]-pt[staa[i]])))q=(q+1)%topp;ret=max(ret,((pt[staa[p]]-pt[staa[i]])^(pt[staa[j]]-pt[staa[i]]))+((pt[staa[j]]-pt[staa[i]])^(pt[staa[q]]-pt[staa[i]])));}}return ret;}int main(){while(~scanf(“%d”,&n)&&n!=-1){for(int i=1;i<=n;i++)cin>>pt[i];sort(pt+1,pt+n+1);top=0,topp=-1;for(int i=1;i<=n;i++){while(top>1&&((pt[i]-pt[sta[top]])^(pt[sta[top]]-pt[sta[top-1]]))>=0)top–;sta[++top]=i;}for(int i=1;i<top;i++){staa[++topp]=sta[i];}top=0;for(int i=1;i<=n;i++){while(top>1&&((pt[i]-pt[sta[top]])^(pt[sta[top]]-pt[sta[top-1]]))<=0)top–;sta[++top]=i;}for(int i=top;i>=1;i–){staa[++topp]=sta[i];}printf(“%.3lf\n”,Rotating_Calipers()/2.0);}}

抱最大的希望，为最大的努力，做最坏的打算