UVA 10173 Smallest Bounding Rectangle(旋转卡壳求最小面积外接矩形)

[cpp] view plain copy

1. #include <queue>  
2. #include <stack>  
3. #include <math.h>  
4. #include <stdio.h>  
5. #include <stdlib.h>  
6. #include <iostream>  
7. #include <limits.h>  
8. #include <string.h>  
9. #include <string>  
10. #include <algorithm>  
11. using namespace std;  
12. const int MAX = 1005;  
13. const double inf = 1e20*1.0;  
14. struct point{ double x,y;};  
15. point c[MAX];  
16. const double eps = 1e-6;  
17. bool dy(double x,double y)  {   return x > y + eps;} // x > y   
18. bool xy(double x,double y)  {   return x < y - eps;} // x < y   
19. bool dyd(double x,double y) {   return x > y - eps;} // x >= y   
20. bool xyd(double x,double y) {   return x < y + eps;}     // x <= y   
21. bool dd(double x,double y)  {   return fabs( x - y ) < eps;}  // x == y  
22. double crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向   
23. {  
24.     return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);  
25. }  
26. double disp2p(point a,point b)  
27. {  
28.     return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));  
29. }  
30. bool cmp(point a,point b)  // 排序     
31. {    
32.     double len = crossProduct(c[0],a,b);    
33.     if( dd(len,0.0) )    
34.         return xy(disp2p(c[0],a),disp2p(c[0],b));    
35.     return xy(len,0.0);    
36. }  
37. double disp2seg(point a,point l1,point l2)  
38. {  
39.     return fabs(crossProduct(a,l1,l2))/disp2p(l1,l2);  
40. }  
41. point foot_line(point a,point l1,point l2)  // 求一个点，使得ab垂直于l1l2   
42. {  
43.     point c;  
44.     l2.x -= l1.x; l2.y -= l1.y;  
45.     c.x = a.x - l1.x - l2.y + l1.x;  
46.     c.y = a.y - l1.y + l2.x + l1.y;  
47.     return c;     
48. }  
49. double rota_angle(point a1,point a2,point b1,point b2) //判断向量a1a2与b1b2的位置   
50. {                                                       //返回b1b2在a1a2的方向   
51.     point t;  
52.     t.x = b2.x - (b1.x - a1.x);  
53.     t.y = b2.y - (b1.y - a1.y);  
54.     return crossProduct(a1,a2,t);  
55. }  
56. double RC_minareaRectangle(point p[],int n)  
57. {  
58.     int r[4];       // 0 == ymin, 1 == xmin, 2 == ymax ,3 == xmax;  
59.     memset(r,0,sizeof(r));  
60.     for(int i=0; i<n; i++)  
61.     {  
62.         if( xy(p[i].y,p[r[0]].y) )  r[0] = i;  
63.         if( xy(p[i].x,p[r[1]].x) )  r[1] = i;  
64.         if( dy(p[i].y,p[r[2]].y) )  r[2] = i;  
65.         if( dy(p[i].x,p[r[3]].x) )  r[3] = i;  
66.     }  
67.     int tp = r[0];  
68.     double area = inf;  
69.     do  
70.     {  
71.         point t = foot_line(p[r[0]],p[r[0]],p[(r[0]+1)%n]);   
72.         while( dy(rota_angle(t,p[r[0]],p[r[1]],p[(r[1]+1)%n]),0.0) )  
73.             r[1]++, r[1] %= n;  
74.           
75.         while( dy(rota_angle(p[r[0]],t,p[r[3]],p[(r[3]+1)%n]),0.0) )  
76.             r[3]++, r[3] %= n;  
77.               
78.         while( dy(disp2seg(p[(r[2]+1)%n],p[r[0]],p[(r[0]+1)%n]),  
79.                 disp2seg(p[r[2]],p[r[0]],p[(r[0]+1)%n])) )  
80.             r[2]++, r[2] %= n;  
81.         double a = disp2seg(p[r[2]],p[r[0]],p[(r[0]+1)%n]);  
82.         t = foot_line(p[r[3]],p[r[0]],p[(r[0]+1)%n]);  
83.         double b = disp2seg(p[r[1]],p[r[3]],t);  
84.         area = min( area, a*b );  
85.         r[0]++; r[0] %= n;  
86.     }while( r[0] != tp );  
87.     return area;  
88. }  
89. point stk[MAX];  
90. int top;  
91. double Graham(int n)  
92. {  
93.     int tmp = 0;    
94.     for(int i=1; i<n; i++)  
95.         if( xy(c[i].x,c[tmp].x) || dd(c[i].x,c[tmp].x) && xy(c[i].y,c[tmp].y) )  
96.             tmp = i;  
97.     swap(c[0],c[tmp]);  
98.     sort(c+1,c+n,cmp);  
99.     stk[0] = c[0]; stk[1] = c[1];  
100.     top = 1;  
101.     for(int i=2; i<n; i++)  
102.     {  
103.         while( xyd( crossProduct(stk[top],stk[top-1],c[i]), 0.0 ) && top >= 1 )  
104.             top--;  
105.         stk[++top] = c[i];  
106.     }  
107.     return RC_minareaRectangle(stk,top+1);  
108. }  
109. int main()  
110. {  
111.     int n;  
112.       
113.     while( ~scanf("%d",&n) && n )  
114.     {  
115.         for(int i=0; i<n; i++)  
116.             scanf("%lf%lf",&c[i].x,&c[i].y);  
117.       
118.         if( n <= 2 )  
119.         {  
120.             printf("0.0000/n");  
121.             continue;  
122.         }  
123.         double ans = Graham(n);  
124.         printf("%.4lf/n",ans);    
125.     }  
126. return 0;  
127. }