首页 > > 程序设计 > C/C++ >

bzoj 1185: [HNOI2007]最小矩形覆盖

2018-06-17 23:15:53来源：未知阅读 ()

%%hzwer，，可以通过蹩脚的画图法发现，矩形的一边会和凸包一边重合。所以就可以枚举边，然后在用旋转卡壳的方法求出左边界，上边界，右边界就是当前的最小面积。

这题细节太神了、、、（应该先做下一题，，，）

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #define eps 1e-8
 5 using namespace std;
 6 double ans=1e60;
 7 int n,top;
 8 struct point{
 9     double x,y;
10     point(){}
11     point(double _x, double _y):x(_x),y(_y){}
12     friend bool operator < (point a, point b){
13         return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;
14     }
15     friend bool operator == (point a, point b){
16         return fabs(a.x-b.x)<eps && fabs(a.y-b.y)<eps;
17     }
18     friend bool operator != (point a, point b){
19         return !(a==b);
20     }
21     friend point operator + (point a, point b){
22         return point(a.x+b.x,a.y+b.y);
23     }
24     friend point operator - (point a, point b){
25         return point (a.x-b.x,a.y-b.y);
26     }
27     friend point operator * (point a, double b){
28         return point (a.x*b,a.y*b);
29     }
30     friend double operator * (point a, point b){
31         return a.x*b.y-a.y*b.x;
32     }
33     friend double operator / (point a, point b){
34         return a.x*b.x+a.y*b.y;
35     }
36     friend double dis(point a){
37         return sqrt(a.x*a.x+a.y*a.y);
38     }
39 }p[50005],q[50005],t[5];
40 bool cmp(point a, point b)
41 {
42     double t=(a-p[1])*(b-p[1]);
43     if (fabs(t)<eps) return dis(p[1]-a)-dis(p[1]-b)<0;
44     return t>0;
45 }
46 void Graham()
47 {
48     for (int i=2; i<=n; i++)
49         if (p[i]<p[1]) swap(p[1],p[i]);
50     sort(p+2,p+n+1,cmp);
51     q[++top]=p[1]; 
52     for (int i=2; i<=n; i++)
53     {
54         while (top>1 && (q[top]-q[top-1])*(p[i]-q[top])<eps) top--;
55         q[++top]=p[i];
56     } 
57     q[0]=q[top];
58 }
59 void RC()
60 {
61     int l=1,r=1,p=1;
62     double L,R,D,H;
63     for (int i=0; i<top; i++)
64     {
65         D=dis(q[i]-q[i+1]);
66         while ((q[i+1]-q[i])*(q[p+1]-q[i])-(q[i+1]-q[i])*(q[p]-q[i])>-eps) p=(p+1)%top;
67         while ((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps) r=(r+1)%top;
68         if (i==0) l=r;
69         while ((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])<eps) l=(l+1)%top;
70         L=(q[i+1]-q[i])/(q[l]-q[i])/D; 
71         R=(q[i+1]-q[i])/(q[r]-q[i])/D;
72         H=(q[i+1]-q[i])*(q[p]-q[i])/D;
73         double tmp=fabs(H)*(R-L);
74         if (tmp<ans)
75         {
76             ans=tmp;
77             t[0]=q[i]+(q[i+1]-q[i])*(R/D);
78             t[1]=t[0]+(q[r]-t[0])*(H/dis(t[0]-q[r]));
79             t[2]=t[1]-(t[0]-q[i])*((R-L)/dis(q[i]-t[0]));
80             t[3]=t[2]-(t[1]-t[0]);
81         }
82     }
83 }
84 int main()
85 {
86     scanf("%d",&n);
87     for (int i=1; i<=n; i++) scanf("%lf%lf",&p[i].x,&p[i].y);
88     Graham(); RC();
89     printf("%.5lf\n",ans);
90     int fir=0;
91     for (int i=1; i<=3; i++)
92         if (t[i]<t[fir]) fir=i;
93     for (int i=0; i<=3; i++)
94         printf("%.5lf %.5lf\n",t[(i+fir)%4].x,t[(i+fir)%4].y);
95     return 0;
96 }