BZOJ1185: [HNOI2007]最小矩形覆盖

1185: [HNOI2007]最小矩形覆盖

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 1795  Solved: 795
[Submit][Status][Discuss]

Description

 

思路{

　　先求凸包,发现矩形的一条边一定与凸多边形的一条边重合.

　　用类似旋转卡壳的方式即可求出对于这条边为底,最左端的点,最右端的点,最远的点,

　　这样直接更新答案就可以了.

}

#include<bits/stdc++.h>
#define RG register
#define il inline 
#define N 50010
#define db double
using namespace std;
#define eps (1e-8)
db Ans=1e60;
struct point{
  db x,y;
  point() {}
  point (db X,db Y):x(X),y(Y) {}
  bool operator <(const point & a)const{return (fabs(y-a.y)<eps)?x<a.x:y<a.y;}
  point operator +(const point & a)const{return point(x+a.x,y+a.y);}
  point operator -(const point & a)const {return point(x-a.x,y-a.y);}
  point operator *(const db & k)const{return point(k*x,k*y);}
  db operator *(const point & a)const{return x*a.y-y*a.x;}
  db operator ^(const point & a)const{return x*a.x+y*a.y;}
  db len(){return sqrt(x*x+y*y);}
}p[N],st[N],q[4];
int n,top;
int cmp(db k){if(fabs(k)<eps)return 0;return k>0?1:-1;}
bool comp(const point & a,const point & b){return cmp(b.x-a.x)?a.x<b.x:a.y<b.y;}
void Graham(){
  sort(p+1,p+n+1,comp);
  for(int i=1;i<=n;++i){
    while(top>1&&(st[top]-st[top-1])*(p[i]-st[top-1])<eps)top--;
    st[++top]=p[i];
  }int NN=top;st[++top]=p[n-1];
  for(int i=n-2;i>1;i--){
    while(top>NN&&(st[top]-st[top-1])*(p[i]-st[top-1])<eps)top--;
    st[++top]=p[i];
  }n=top;
  for(int i=1;i<=top;++i)p[i]=st[i],p[0]=st[top];
}
void RC(){
  int l(1),r(1),u(1);
  db L,R,H,d;
  for(int i=0;i<top;++i){
    d=(p[i+1]-p[i]).len();
    while((p[i+1]-p[i])*(p[u+1]-p[i])-(p[i+1]-p[i])*(p[u]-p[i])>-eps)u=(u+1)%n;
    while(((p[r+1]-p[i])^(p[i+1]-p[i]))-((p[r]-p[i])^(p[i+1]-p[i]))>-eps)r=(r+1)%n;
    if(!i)l=r;
    while(((p[l+1]-p[i])^(p[i+1]-p[i]))-((p[l]-p[i])^(p[i+1]-p[i]))<eps)l=(l+1)%n;
    L=((p[l]-p[i])^(p[i+1]-p[i]))/d;
    R=((p[r]-p[i])^(p[i+1]-p[i]))/d;
    H=((p[i+1]-p[i])*(p[u]-p[i]))/d;
    if(H<0)H=-H;
    db tmp=(R-L)*H;
    if(tmp<Ans){
      Ans=tmp;
      q[0]=p[i]+(p[i+1]-p[i])*(R/d);
      q[1]=q[0]+(p[r]-q[0])*(H/(q[0]-p[r]).len());
      q[2]=q[1]-(q[0]-p[i])*((R-L)/(p[i]-q[0]).len());
      q[3]=q[2]-(q[1]-q[0]);
    }
  }
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
  Graham();RC();printf("%.5lf
",Ans);
  int s(0);
  for(int i=1;i<=3;++i)if(q[i]<q[s])s=i;
  for(int i=0;i<=3;++i){
    printf("%.5lf %.5lf
",q[(i+s)%4].x,q[(i+s)%4].y);
  }
  return 0;
}