Lvat_s Blog

旋转卡壳模版题

首先搞出凸包，然后在凸包上面扫描，用两个指针维护单调性

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cstring>
#include<algorithm>
using namespace std;

int n,St_size,St[2005];
double ans;

struct Point{
double x,y;
Point(){}
Point(int sa,int sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend double operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
friend bool operator<(Point A,Point B){return A.y<B.y || A.y==B.y && A.x<B.x;}
}poi[2005];

double Abs(double x){return x>0?x:-x;}
double Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}

bool cmp(Point A,Point B){
int Mul=(int)((A-poi[1])*(B-poi[1]));
return (Mul>0)||(Mul==0 && Dist(A,poi[1])<Dist(B,poi[1]));
}

void Graham(){
if(n==1){St[1]=1;St_size=1;return;}
St[1]=1;
St[2]=2;
St_size=2;
for(int i=3;i<=n;i++){
	while(St_size>1 && (poi[St[St_size]]-poi[St[St_size-1]])*(poi[i]-poi[St[St_size-1]])<=0)St_size--;
	St[++St_size]=i;
}
}

void Prepare(){
int pos=1;
for(int i=2;i<=n;i++)if(poi[i]<poi[pos])pos=i;
swap(poi[pos],poi[1]);
sort(poi+2,poi+n+1,cmp);
}

void RC(){
St[St_size+1]=1;
for(int i=1;i<=St_size;i++){
	int poix=i%St_size+1,poiy=(i+2)%St_size+1;
	for(int j=i+2;j<=St_size;j++){
		while(poix%St_size+1!=j && Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix+1]]-poi[St[i]]))>Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]])))poix=poix%St_size+1;
		while(poiy%St_size+1!=i && Abs((poi[St[poiy+1]]-poi[St[i]])*(poi[St[j]]-poi[St[i]]))>Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])))poiy=poiy%St_size+1;
		ans=max(ans,Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]]))+Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])));
	}
}
}

int main(){
freopen("1069.in","r",stdin);
freopen("1069.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%lf %lf",&poi[i].x,&poi[i].y);}
Prepare();
Graham();
RC();
printf("%.3lf\n",ans/2);
return 0;
}