UVA 10652凸包+面的旋转

  1 /*
  2 
  3 UVA 10652计算几何
  4 凸包+面的旋转
  5 就凸包部分而言，是模板。
  6 这道题有个小障碍，就是有确定的图形中心点和转动角度，确定转动后的顶点的坐标。
  7 我的方法是，先转动中心点向顶点的向量，再中心加上这个向量。这应该是普适的。
  8 */
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 #include <string.h>
 12 #include <math.h>
 13 #include <ctype.h>
 14 #include <string>
 15 #include <iostream>
 16 #include <sstream>
 17 #include <vector>
 18 #include <queue>
 19 #include <stack>
 20 #include <map>
 21 #include <list>
 22 #include <set>
 23 #include <algorithm>
 24 #define INF 0x3f3f3f3f
 25 #define eps 1e-7
 26 #define eps2 1e-3
 27 #define zero(x) (((x)>0?(x):-(x))<eps)
 28 using namespace std;
 29 
 30 
 31 struct Point
 32 {
 33     double x,y;
 34     Point() {}
 35     Point(double xx,double yy)
 36     {
 37         x=xx;
 38         y=yy;
 39     }
 40     bool operator<(const Point& p) const{
 41         if (x==p.x) return y<p.y;
 42         else return x<p.x;
 43     }
 44 }P1[2505],P2[2505];
 45 
 46 typedef Point Vector;
 47 
 48 bool operator==(Point A,Point B)
 49 {
 50     if ((fabs(A.x-B.x)<eps) && (fabs(A.y-B.y)<eps)) return true;
 51     else return false;
 52 }
 53 Vector operator-(Point A,Point B)//表示A指向B
 54 {
 55     return Vector(A.x-B.x,A.y-B.y);
 56 }
 57 Vector operator*(Vector A,double k)
 58 {
 59     return Vector(A.x*k,A.y*k);
 60 }
 61 Vector operator+(Point A,Point B)//表示A指向B
 62 {
 63     return Vector(B.x+A.x,B.y+A.y);
 64 }
 65 double Dot(Vector A,Vector B)
 66 {
 67     return A.x*B.x+A.y*B.y;
 68 }
 69 double Length(Vector A)
 70 {
 71     return sqrt(Dot(A,A));
 72 }
 73 double Cross(Vector A,Vector B)
 74 {
 75     return A.x*B.y-A.y*B.x;
 76 }
 77 double Area2(Point A,Point B,Point C)
 78 {
 79     return Cross(B-A,C-A);
 80 }
 81 int dcmp(double x)
 82 {
 83     if(fabs(x)<eps) return 0;
 84     else if(x>0) return 1;
 85     else return -1;
 86 }
 87 double angle(Vector v)
 88 {
 89     return atan2(v.y,v.x);
 90 }
 91 Vector Rotate(Vector A,double rad)//向量向逆时针旋转
 92 {
 93     return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
 94 }
 95 
 96 //p是原先点的数组，n是个数，ch是凸包的点集
 97 //精度要求高是用dcmp比较
 98 //返回凸包点的个数
 99 int ConvexHull(Point *p, int n, Point* ch){        //求凸包
100     sort(p, p + n);//先按照x，再按照y
101     int m = 0;
102     for(int i = 0; i < n; i++){
103         while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) m--;
104         ch[m++] = p[i];
105     }
106     int k = m;
107     for(int i = n-2; i >= 0; i--){
108         while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) < 0) m--;
109         ch[m++] = p[i];
110     }
111     if(n > 1) m--;
112     return m;
113 }
114 double ConvexPolygonArea(Point *p, int n){//凸包面积
115     double area = 0;
116     for(int i = 1; i < n-1; i++) area += Area2(p[0], p[i], p[i+1]);
117     return area / 2;
118 }
119 
120 double x,y,w,h,arf;
121 int t,n,cnt1,cnt2;
122 int main()
123 {
124     cin>>t;
125     while(t--)
126     {
127         double area1=0,area2=0;
128         cnt1=0;
129         cin>>n;
130         for(int i=0;i<n;i++)
131         {
132             cin>>x>>y>>w>>h>>arf;
133             arf=arf/180*M_PI;
134             area1+=w*h;
135             Vector v[4];//四个方向上的向量
136             v[0].x=w/2;v[0].y=h/2;
137             v[1].x=-w/2;v[1].y=h/2;
138             v[2].x=-w/2;v[2].y=-h/2;
139             v[3].x=w/2;v[3].y=-h/2;
140             for(int j=0;j<4;j++)//构造4个顶点
141             {
142                 Vector nv=Rotate(v[j],2*M_PI-arf);
143                 P1[cnt1].x=nv.x+x;
144                 P1[cnt1++].y=nv.y+y;
145             }
146         }
147         sort(P1,P1+cnt1);
148         int cnt2=ConvexHull(P1,cnt1,P2);
149         area2=ConvexPolygonArea(P2,cnt2);
150         double ans=area1/area2*100;
151         printf("%.1lf %%
",ans);
152     }
153     return 0;
154 }