struct ConvexHull
{
const static int __=1e5+5;
point ch[__];int n;
static bool cmp(const point &x,const point &y)
{
if(x.x==y.x)
return x.y<y.y;
return x.x<y.x;
}
point& operator[](int x){return ch[x];}
void add(point &p,int lim)
{
while(n>=lim && ((p-ch[n-1])^(ch[n]-ch[n-1]))>0)
--n;
ch[++n].set(p.x,p.y);
}
ConvexHull() {clear();}
void get_ConvexHull(point p[],int np)
{
sort(p+1,p+1+np,cmp);
n=0;
for(int i=1;i<=np;++i)
add(p[i],2);
for(int i=np-1,j=n;i>=1;--i)
add(p[i],j+1);
--n;
}
//周长(若凸包为直线需要除以2)
double circumference()
{
ch[n+1]=ch[1];
double res=0.0;
for(int i=1;i<=n;++i)
res+=line(ch[i],ch[i+1]).length();
return res;
}
void print()
{
for(int i=1;i<=n;++i)
printf("%.2f %.2f\n",(double)ch[i].x,(double)ch[i].y);
}
void clear(){n=0;}
}C;
旋转卡壳:
struct point
{
ll x,y;
point(ll x=0,ll y=0):
x(x),y(y) {}
friend ll operator*(const point& a,const point& b)
{
return a.x*b.y-a.y*b.x;
}
};
point p[100005],tb[100005];
bool cmp(const point& a,const point& b)
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
double cross(const point& st,const point& fir,const point& sec)
{
double x1=fir.x-st.x,y1=fir.y-st.y;
double x2=sec.x-st.x,y2=sec.y-st.y;
return x1*y2-x2*y1;
}
point xl(const point& a,const point& b)//向量b->a
{
return point(a.x-b.x,a.y-b.y);
}
int tubao(int n)
{
sort(p+1,p+n+1,cmp);
int m=0;
for(int i=1; i<=n; i++)
{
while(m>1 && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
tb[m++]=p[i];
}
int temp=m;
for(int i=n-1; i>=1; i--)
{
while(m>temp && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
tb[m++]=p[i];
}
if(n>1)m--;
// for(int i=0;i<m;i++)
// printf("p: %d %d\n",tb[i].x,tb[i].y);
return m;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(p,0,sizeof(p));
memset(tb,0,sizeof(tb));
for(int i=1; i<=n; i++)
scanf("%lld%lld",&p[i].x,&p[i].y);
int m=tubao(n);
tb[m]=tb[0];
int x=2;
ll ans=0;
for(int i=0; i<=m-1; i++)
{
while(cross(tb[x],tb[i],tb[(i+1)%m])<
cross(tb[(x+1)%m],tb[i],tb[(i+1)%m]))
x=(x+1)%m;
ans=max(ans,(tb[x].x-tb[i].x)*(tb[x].x-tb[i].x)
+(tb[x].y-tb[i].y)*(tb[x].y-tb[i].y));
ans=max(ans,(tb[x].x-tb[(i+1)%m].x)*(tb[x].x-tb[(i+1)%m].x)
+(tb[x].y-tb[(i+1)%m].y)*(tb[x].y-tb[(i+1)%m].y));
}
printf("%lld\n",ans);
}
return 0;
}
旋转卡壳:
struct point
{
ll x,y;
point(ll x=0,ll y=0):
x(x),y(y) {}
friend ll operator*(const point& a,const point& b)
{
return a.x*b.y-a.y*b.x;
}
};
point p[50005],tb[50005];
bool cmp(const point& a,const point& b)
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
double cross(const point& st,const point& fir,const point& sec)
{
double x1=fir.x-st.x,y1=fir.y-st.y;
double x2=sec.x-st.x,y2=sec.y-st.y;
return x1*y2-x2*y1;
}
point xl(const point& a,const point& b)//向量b->a
{
return point(a.x-b.x,a.y-b.y);
}
int tubao(int n)
{
sort(p+1,p+n+1,cmp);
int m=0;
for(int i=1; i<=n; i++)
{
while(m>1 && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
tb[m++]=p[i];
}
int temp=m;
for(int i=n-1; i>=1; i--)
{
while(m>temp && xl(p[i],tb[m-2])*xl(tb[m-1],tb[m-2])>=0)m--;
tb[m++]=p[i];
}
if(n>1)m--;
// for(int i=0;i<m;i++)
// printf("p: %lld %lld\n",tb[i].x,tb[i].y);
return m;
}
int main()
{
int n;
while(~scanf("%d",&n) && ~n)
{
memset(p,0,sizeof(p));
memset(tb,0,sizeof(tb));
for(int i=1; i<=n; i++)
scanf("%lld%lld",&p[i].x,&p[i].y);
int m=tubao(n);
tb[m]=tb[0];
double ans=0;
int fir=1,sec=2;
for(int i=0; i<=m-1; i++)
{
while(1)
{
while(cross(tb[i],tb[fir],tb[sec])<cross(tb[i],tb[fir],tb[(sec+1)%m]))
sec=(sec+1)%m;
while(cross(tb[i],tb[fir],tb[sec])<cross(tb[i],tb[(fir+1)%m],tb[sec]))
fir=(fir+1)%m;
if((cross(tb[i],tb[fir],tb[sec])>=cross(tb[i],tb[(fir+1)%m],tb[sec]))
&&(cross(tb[i],tb[fir],tb[sec])>=cross(tb[i],tb[fir],tb[(sec+1)%m])))
break;
}
ans=max(ans,fabs(cross(tb[i],tb[fir],tb[sec]))/2.0);
}
printf("%.2f\n",ans);
}
return 0;
}
