●UVA 10652 Board Wrapping

世事洞明皆学问，人情练达即文章。这篇文章主要讲述●UVA 10652 Board Wrapping相关的知识，希望能为你提供帮助。

题链：
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\n",cnt); area2=PolygonArea(cnt); printf("%.1lf %%\n",area1*100/area2); } return 0; }

【●UVA 10652 Board Wrapping】