题链：
https://vjudge.net/problem/UVA-10652
题解：
计算几何，Andrew求凸包，
裸题。。。（数组开小了，还整了半天。。。）
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 650
using namespace std;
const double eps=1e-8,Pi=acos(-1);
int sign(double x){
if(fabs(x)<=eps) return 0;
return x<0?-1:1;
}
struct Point{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
};
typedef Point Vector;
bool operator < (const Point A,const Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}
bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}
double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}
Point D[MAXN*4],C[MAXN*4];
double torad(double deg){return deg/180*Pi;}//角度转弧度
Vector rotate(Vector A,double angle){//向量A逆时针旋转angle（弧度）
return Vector(A.x*cos(angle)-A.y*sin(angle),A.x*sin(angle)+A.y*cos(angle));
}
int Andrew(int dnt){
int cnt=0,k=0;
sort(D+1,D+dnt+1);
dnt=unique(D+1,D+dnt+1)-D-1;
for(int i=1;i<=dnt;i++){
while(cnt>1&&((C[cnt]-C[cnt-1])^(D[i]-C[cnt-1]))<=0) cnt--;
C[++cnt]=D[i];
} k=cnt;
for(int i=dnt-1;i>=1;i--){
while(cnt>k&&((C[cnt]-C[cnt-1])^(D[i]-C[cnt-1]))<=0) cnt--;
C[++cnt]=D[i];
}
return cnt;
}
double PolygonArea(int cnt){
double area=0;
for(int i=1;i<cnt;i++) area+=(C[i]^C[i+1])/2;
return area;
}
int main(){
double area1,area2,x,y,w,h,angle;
int Case,N,dnt,cnt; scanf("%d",&Case);
while(Case--){
area1=area2=dnt=cnt=0;
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&angle);
angle=-torad(angle);
D[++dnt]=Point(x,y)+rotate(Vector(w/2,h/2),angle);
D[++dnt]=Point(x,y)+rotate(Vector(-w/2,h/2),angle);
D[++dnt]=Point(x,y)+rotate(Vector(w/2,-h/2),angle);
D[++dnt]=Point(x,y)+rotate(Vector(-w/2,-h/2),angle);
area1+=w*h;
}
cnt=Andrew(dnt);
//printf("%d
",cnt);
area2=PolygonArea(cnt);
printf("%.1lf %%
",area1*100/area2);
}
return 0;
}