[HNOI2007]最小矩形覆盖

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge

Submit: 2081  Solved: 920

[][][]

Description

给定一些点的坐标，要求求能够覆盖所有点的最小面积的矩形，

输出所求矩形的面积和四个顶点坐标

 

Input

第一行为一个整数n（3<=n<=50000）

从第2至第n+1行每行有两个浮点数，表示一个顶点的x和y坐标，不用科学计数法

 

Output

第一行为一个浮点数，表示所求矩形的面积（精确到小数点后5位），

接下来4行每行表示一个顶点坐标，要求第一行为y坐标最小的顶点，

其后按逆时针输出顶点坐标.如果用相同y坐标，先输出最小x坐标的顶点

Sample Input

6 1.0 3.00000

1 4.00000

2.0000 1

3 0.0000

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

HINT

 

Source

[ ][ ][ ]

 Back

 

首先有一个结论，矩形的一条边一定在凸包上！！！

枚举凸包上的边

用旋转卡壳在凸包上找矩形另外三点。。

差不多吧，其它三个点可以找的吧，而且也是有单调性的。

1 #pragma GCC optimize(2) 2 #pragma G++ optimize(2) 3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8  9 #define eps 0.0000000110 #define N 5000711 using namespace std;12 inline int read()13 {14     int x=0,f=1;char ch=getchar();15     while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}16     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}17     return x*f;18 }19 20 int n,tot;21 double ans=1e60;22 struct P23 {24     double x,y;25     P(){}26     P(double _x,double _y):x(_x),y(_y){}27     friend bool operator<(P a,P b){
    return fabs(a.y-b.y)
           
            
             
              0;43 }44 void Graham()45 {46 for (int i=2;i<=n;i++)47 if(p[i]
              
               1&&(q[tot]-q[tot-1])*(p[i]-q[tot])
               
                -eps)p=(p+1)%tot;65 while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%tot;66 if(i==0)l=r;67 while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])