UVA-10652 凸包

题意：

给n个矩形,问包含这些矩形的尽量小的凸多边形的面积是多少;

思路：

由于给的矩形的形式是给出了中心的坐标,长和宽以及旋转的角度,所以先转换成四个点的坐标,然后求一遍凸包就好了,第一次写凸包,代码都是白书上的;

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map>
 
using namespace std;
 
#define Fori,j,n) forint i=j;i<=n;i++)
#define mstss,b) memsetss,b,sizeofss));
 
typedef  long long LL;
 
template<class T> void readT&num) {
    char CH; bool F=false;
    forCH=getchar);CH<'0'||CH>'9';F= CH=='-',CH=getchar));
    fornum=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar));
    F && num=-num);
}
int stk[70], tp;
template<class T> inline void printT p) {
    if!p) { puts"0"); return; }
    whilep) stk[++ tp] = p%10, p/=10;
    whiletp) putcharstk[tp--] + '0');
    putchar'
');
}
 
const LL mod=1e9+7;
const double PI=acos-1.0);
const int inf=1e9;
const int N=1e5+20;
const int maxn=1e6+4;
const double eps=1e-12;

struct Point
{
    double x,y;
    Point double x=0,double y=0):xx),yy) {}
};
typedef Point Vector;
Vector operator + Vector A,Vector B){return VectorA.x+B.x,A.y+B.y);}
Vector operator - Vector A,Vector B){return VectorA.x-B.x,A.y-B.y);}
Vector operator * Vector A,double p){return VectorA.x*p,A.y*p);}
Vector operator / Vector A,double p){return VectorA.x/p,A.y/p);}
bool operator < const Point& a,const Point& b){return a.x<b.x||a.x==b.x&&a.y<b.y);}
Vector RotateVector A,double rad){return VectorA.x*cosrad)-A.y*sinrad),A.x*sinrad)+A.y*cosrad));}
int dcmpdouble x){iffabsx)<eps) return 0;else return x<0 ? -1:1;}
bool operator == const Point& a,const Point& b){return dcmpa.x-b.x)==0&&dcmpa.y-b.y)==0;}

double DotVector A,Vector B){return A.x*B.x+A.y*B.y;}
double LengthVector A){return sqrtDotA,A));}
double AngleVector A,Vector B){return acosDotA,B)/LengthA)/LengthB));}
double CrossVector A,Vector B){return A.x*B.y-A.y*B.x;}

int ConvexHullPoint *p,int n,Point *ch)
{
    sortp,p+n);
    int m=0;
    forint i=0;i<n;i++)
    {
        whilem>1&&Crossch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    int k=m;
    forint i=n-2;i>=0;i--)
    {
        whilem>k&&Crossch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    ifn>1)m--;
    return m;
}
double AreaPoint *p,int n)
{
    double area=0;
    forint i=1;i<n-1;i++)area+=Crossp[i]-p[0],p[i+1]-p[0]);
    return area/2;
}

int main)
{
    Point P[2410],ch[2410];
    int t;
    readt);
    whilet--)
    {
        int n,cnt=0;
        double sum=0;
        readn);
        double x,y,w,h,j,ang;
        Fori,1,n)
        {
            scanf"%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);
            sum+=w*h;
            Point ox,y);
            ang=-j*PI/180;
            P[cnt++]=o+RotateVector-w/2,-h/2),ang);
            P[cnt++]=o+RotateVector-w/2,h/2),ang);
            P[cnt++]=o+RotateVectorw/2,-h/2),ang);
            P[cnt++]=o+RotateVectorw/2,h/2),ang);
        }
        int m=ConvexHullP,cnt,ch);
        double ans=100*sum/Areach,m);
        printf"%.1lf %%
",ans);
    }
    return 0;
}