1185: [HNOI2007]最小矩形覆盖

Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge
Submit: 1426 Solved: 648
[Submit][Status][Discuss]
Description

1185: [HNOI2007]最小矩形覆盖-LMLPHP
Input

Output

Sample Input

Sample Output

HINT

Source

计算几何 vfleaking提供Spj
#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=1e5+;

const double eps=1e-;

double ans=1e60;

struct Vector{

    double x,y;

    Vector(double x=,double y=):x(x),y(y){}

}p[N],q[N],t[];int n,top;

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}

Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}

double operator * (Vector A,Vector B){return A.x*B.y-A.y*B.x;;}

double operator / (Vector A,Vector B){return A.x*B.x+A.y*B.y;;}

bool operator<(Vector a,Vector b){

    return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;

}

bool operator==(Vector a,Vector b){

    return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;

}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}

double Length(Vector A){return sqrt(Dot(A,A));}

double Angle(Vector A,Vector B){return acos(Dot(A,B)/(Length(A)*Length(B)));}

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double Area2(Vector A,Vector B,Vector C){return Cross(B-A,C-A);}

bool cmp(Vector a,Vector b){

    double t=(a-p[])*(b-p[]);

    if(fabs(t)<eps) return Length(p[]-a)-Length(p[]-b)<;

    else return t>;

}

void graham(){//凸包

    for(int i=;i<=n;i++) if(p[i]<p[]) swap(p[i],p[]);

    sort(p+,p+n+,cmp);

    q[++top]=p[];

    for(int i=;i<=n;i++){

        while(top>&&(q[top]-q[top-])*(p[i]-q[top])<eps) top--;

        q[++top]=p[i];

    }

    q[]=q[top];

}

void RC(){//旋转卡壳

    int l=,r=,p=;

    double L,R,D,H;

    for(int i=;i<top;i++){

        D=Length(q[i]-q[i+]);

        while((q[i+]-q[i])*(q[p+]-q[i])-(q[i+]-q[i])*(q[p]-q[i])>-eps) p=(p+)%top;

        while((q[i+]-q[i])/(q[r+]-q[i])-(q[i+]-q[i])/(q[r]-q[i])>-eps) r=(r+)%top;

        if(i==) l=r;

        while((q[i+]-q[i])/(q[l+]-q[i])-(q[i+]-q[i])/(q[l]-q[i])<eps) l=(l+)%top;

            L=(q[i+]-q[i])/(q[l]-q[i])/D,R=(q[i+]-q[i])/(q[r]-q[i])/D;

        H=(q[i+]-q[i])*(q[p]-q[i])/D;

        if(H<) H=-H;

        double tmp=(R-L)*H;

        if(tmp<ans){

            ans=tmp;

            t[]=q[i]+(q[i+]-q[i])*(R/D);

            t[]=t[]+(q[r]-t[])*(H/Length(t[]-q[r]));

            t[]=t[]-(t[]-q[i])*((R-L)/Length(q[i]-t[]));

            t[]=t[]-(t[]-t[]);

        }

    }

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);

    graham();

    RC();

    printf("%.5lf\n",ans);

    int fir=;

    for(int i=;i<;i++) if(t[i]<t[fir]) fir=i;

    for(int i=;i<;i++){//某些OJ评测卡精度.. 比如，洛谷

        if(fabs(t[(i+fir)%].x)<1e-) printf("0.00000 ");else printf("%.5lf ",t[(i+fir)%].x);

        if(fabs(t[(i+fir)%].y)<1e-) printf("0.00000\n");else printf("%.5lf\n",t[(i+fir)%].y);

    }

    return ;

}

/*

Sample Input

6

1.0 3.00000

1 4.00000

2.00000 1

3 0.00000

3.00000 6

6.0 3.0

Sample Output

18.00000

3.00000 0.00000

6.00000 3.00000

3.00000 6.00000

0.00000 3.00000

*/