刘汝佳《算法竞赛入门经典》P272例题6包装木板
题意：有n块矩形木板，你的任务是用一个面积尽量小的凸多边形把它们抱起来，并计算出木板占整个包装面积的百分比。
输入：t组数据，每组先输入木板个数n，接下来n行，每行x,y,w,h,j。(x,y)是木板中心的坐标，w是宽，h是高，j是顺时针旋转的角度。
木板互不相交。
输出：对于每组数据，输出木板总面积占包装总面积的百分比，保留小数点后1位。
题解：典型的二维凸包问题，理解并调用模板即可。
附上凸包的证明过程，只看网址里的图，注意sort是极角排序：传送门。
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef struct Point{
double x,y;
Point(double x=,double y=):x(x),y(y){}
}Vector;
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);
}
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
Vector Rotate(Vector A,double rad) //向量旋转
{
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
double ConvexPolygonArea(Point *p,int n)
{
double area=;
for(int i=;i<n-;i++)
area+=Cross(p[i]-p[],p[i+]-p[]);
return area/;
}
double torad(double deg)
{
return deg/*acos(-);
}
int ConvexHull(Point *p,int n,Point* ch) //注意是*ch
{
sort(p,p+n);
//不知道这里为什么不能加unique函数
//n=unique(p,p+n)-p;
int m=;
for(int i=;i<n;i++)
{
while(m>&&Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-;i>=;i--) //注意是--不是++
{
while(m>k&&Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
return m;//别忘了加m
}
int main()
{
int T;
Point P[],ch[];
scanf("%d",&T);
while(T--)
{
int n,pc=;
double area1=;
scanf("%d",&n);
for(int i=;i<n;i++)
{
double x,y,w,h,j,ang;
scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);
Point o(x,y);
ang=-torad(j);
P[pc++]=o+Rotate(Vector(-w/,-h/),ang);
P[pc++]=o+Rotate(Vector(w/,-h/),ang);
P[pc++]=o+Rotate(Vector(-w/,h/),ang);
P[pc++]=o+Rotate(Vector(w/,h/),ang);
area1+=w*h; //矩形总面积
}
int m=ConvexHull(P,pc,ch);
double area2=ConvexPolygonArea(ch,m); //凸包面积
//%被看做是格式说明符 所以要输出两个百分号
printf("%.1lf %%\n",area1*/area2);
}
return ;
}