BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义) - c++编程基础

x+a.y*b.y;}
friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);}
friend P operator-(P a,V b){return P(a.x-b.x,a.y-b.y);}
friend V operator~(V a){return V(a.y,-a.x);}
double dis2(){return x*x+y*y; }
}c[MAXN];
int cmp(P A,P B)
{
double tmp=V(a[1],A)*V(a[1],B);
if (tmp>0) return 1;
else if (fabs(tmp)0);
return 0;
}
int n;

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for (int i=2;i<=n;i++) if (a[i] sort(a+2,a+1+n,cmp);
s[1]=a[1];size=1;
for (int i=2;i<=n;)
if (size<2||V(s[size-1],s[size])*V(s[size],a[i])>eps) s[++size]=a[i++];
else size--;
s[0]=s[size];

int l=1,r=1,t=1;
for (int i=0;i {
while (V(s[i],s[i+1])*V(s[i],s[t+1])-V(s[i],s[i+1])*V(s[i],s[t])>-eps) t=(t+1)%size;
while (V(s[i],s[i+1])/V(s[i],s[r+1])-V(s[i],s[i+1])/V(s[i],s[r])>-eps) r=(r+1)%size;
if (i==0) l=r;
while (V(s[i],s[i+1])/V(s[i],s[l+1])-V(s[i],s[i+1])/V(s[i],s[l]) double Dis2=dis2(s[i],s[i+1]),wlxdis=V(s[i],s[i+1])/V(s[i],s[l]),wrxdis=V(s[i],s[i+1])/V(s[i],s[r]),hxdis=V(s[i],s[i+1])*V(s[i],s[t]);
double tmp=hxdis*(wrxdis-wlxdis)/Dis2;
if (tmp<0) tmp=-tmp;
if (ans>tmp)
{
ans=tmp;
ansp[0]=s[i]-(wlxdis/Dis2)*V(s[i+1],s[i]);
ansp[1]=s[i]+(wrxdis/Dis2)*V(s[i],s[i+1]);
ansp[2]=ansp[1]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
ansp[3]=ansp[0]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
}
}
int p=0;
for (int i=1;i<4;i++) if (ansp[i] printf("%.5lf\n",ans);
for (int i=0;i<4;i++)
printf("%.5lf %.5lf\n",ansp[(p+i)%4].x,ansp[(p+i)%4].y);
return 0;
}

BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义) (二)