uva 10652 Board Wrapping

主要是凸包的应用；
  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #define eps 1e-9
  7 using namespace std;
  8 const double pi = acos(-1);
  9 
 10 int dcmp(double x)
 11 {
 12     return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
 13 }
 14 
 15 struct Point
 16 {
 17     double x;
 18     double y;
 19 
 20     Point(double x = 0, double y = 0):x(x), y(y) {}
 21 
 22     bool operator < (const Point& e) const
 23     {
 24         return dcmp(x - e.x) < 0 || (dcmp(x - e.x) == 0 && dcmp(y - e.y) < 0);
 25     }
 26 
 27     bool operator == (const Point& e) const
 28     {
 29         return dcmp(x - e.x) == 0 && dcmp(y - e.y) == 0;
 30     }
 31 };
 32 
 33 typedef Point Vector;
 34 
 35 Vector operator + (Point A, Point B)
 36 {
 37     return Vector(A.x + B.x, A.y + B.y);
 38 }
 39 
 40 Vector operator - (Point A, Point B)
 41 {
 42     return Vector(A.x - B.x, A.y - B.y);
 43 }
 44 
 45 Vector operator * (Point A, double p)
 46 {
 47     return Vector(A.x * p, A.y * p);
 48 }
 49 
 50 Vector operator / (Point A, double p)
 51 {
 52     return Vector(A.x / p, A.y / p);
 53 }
 54 
 55 double cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
 56 Point rotate(Point a,double ang){return Point(a.x*cos(ang)-a.y*sin(ang),a.x*sin(ang)+a.y*cos(ang));}
 57 int convexhull(Point *p,int n,Point *ch)
 58 {
 59     sort(p,p+n);
 60     int m=0;
 61     for(int i=0;i<n;i++)
 62     {
 63         while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
 64         ch[m++]=p[i];
 65     }
 66     int k=m;
 67     for(int i=n-2;i>=0;i--)
 68     {
 69         while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
 70         ch[m++]=p[i];
 71     }
 72     if(n>1)m--;
 73     return m;
 74 }
 75 Point p[2500],ch[2500];
 76 int main()
 77 {
 78     int t,n;
 79     double alph,x,y,h,w,area1,area2;
 80     scanf("%d",&t);
 81     while(t--)
 82     {
 83         area1=area2=0;
 84         scanf("%d",&n);
 85         int pc=0;
 86         for(int i=0;i<n;i++)
 87         {
 88             scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&alph);
 89             Point o(x,y);
 90             double ang=-(alph*pi/180);
 91             p[pc++]=o+rotate(Point(-w/2,-h/2),ang);
 92             p[pc++]=o+rotate(Point(w/2,-h/2),ang);
 93             p[pc++]=o+rotate(Point(-w/2,h/2),ang);
 94             p[pc++]=o+rotate(Point(w/2,h/2),ang);
 95             area1+=w*h;
 96         }
 97         int m=convexhull(p,pc,ch);
 98         for(int i=1;i<m;i++)
 99             area2+=cross(ch[i]-ch[0],ch[i+1]-ch[0]);
100         area2/=2;
101         printf("%.1lf ",area1/area2*100);
102         puts("%");
103     }
104     return 0;
105 }
View Code