CF-281C Rectangle Puzzle（凸包+面积）

题意：https://codeforces.com/problemset/problem/281/C

就存个模板

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>//sprintf islower isupper
#include <cstdlib>//malloc  exit strcat itoa system("cls")
#include <iostream>//pair
#include <fstream>//freopen("C:\Users\13606\Desktop\Input.txt","r",stdin);
#include <bitset>
//#include <map>
//#include<unordered_map>
#include <vector>
#include <stack>
#include <set>
#include <string.h>//strstr substr strcat
#include <string>
#include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
#include <cmath>
#include <deque>
#include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
#include <vector>//emplace_back
//#include <math.h>
#include <cassert>
#include <iomanip>
//#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
#include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
//******************
clock_t __START,__END;
double __TOTALTIME;
void _MS(){__START=clock();}
void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
//***********************
#define rint register int
#define fo(a,b,c) for(rint a=b;a<=c;++a)
#define fr(a,b,c) for(rint a=b;a>=c;--a)
#define mem(a,b) memset(a,b,sizeof(a))
#define pr printf
#define sc scanf
#define ls rt<<1
#define rs rt<<1|1
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const db E=2.718281828;
const db PI=acos(-1.0);
const ll INF=(1LL<<60);
const int inf=(1<<30);
const db ESP=1e-9;
const int mod=(int)1e9+7;
const int N=(int)1e6+10;

bool zero(double x){
    return (x>0?x:-x)<ESP;
}
struct point
{
    double x,y;
};
struct line
{
    point a,b;
};
//计算 cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//计算 dot product (P1-P0).(P2-P0)
double dmult(point p1,point p2,point p0){
    return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
//两点距离
double distance(point p1,point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool isIntersected(point s1,point e1, point s2,point e2){
    return    (max(s1.x,e1.x) >= min(s2.x,e2.x))&&
              (max(s2.x,e2.x) >= min(s1.x,e1.x))&&
              (max(s1.y,e1.y) >= min(s2.y,e2.y))&&
              (max(s2.y,e2.y) >= min(s1.y,e1.y))&&
              (xmult(s1,s2,e1)*xmult(s1,e1,e2)>0)&&
              (xmult(s2,s1,e2)*xmult(s2,e2,e1)>0);
}
point intersection(point u1,point u2,point v1,point v2){
    point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
             /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}


//点以原点逆时针旋转α度
point rotate(point p0,double alpha){
    alpha=alpha/180*PI;
    return {p0.x*cos(alpha)-p0.y*sin(alpha),p0.y*cos(alpha)+p0.x*sin(alpha)};
}

point Pin[20];
int cmp(point a,point b)  ///设<p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集（如果有多个点有相同的极角，除了距p0最远的点外全部移除)
{
    if(xmult(a,b,Pin[1])>ESP)
        return 1;
    if(fabs(xmult(a,b,Pin[1]))<ESP&&distance(b,Pin[1])-distance(a,Pin[1])>ESP)
        return 1;
    return 0;
}

point Stack[N];
int top;
void Graham(int n,point p[])
{
    top=3;///栈顶在2，因为凸包的前两个点是不会变了
    sort(p+2,p+1+n,cmp);
    Stack[1]=p[1];///压p0p1p2进栈S
    Stack[2]=p[2];
    Stack[3]=p[3];
    for(int i=4;i<=n;i++){
        while(top>=1&&xmult(p[i],Stack[top],Stack[top-1])>ESP){///有了更好的选择
            top--;
        }
        Stack[++top]=p[i];
    }
}
double getArea()
{
    double sum=fabs(xmult(Stack[2],Stack[3],Stack[1]));
    for(int i=3;i<top;i++)
        sum+=fabs(xmult(Stack[i],Stack[i+1],Stack[1]));
    return sum/2.0;
}

int main()
{
    double w,h,alpha;
    sc("%lf%lf%lf",&w,&h,&alpha);
    if(alpha==0||alpha==180)
    {
        pr("%.10lf
",w*h);
        return 0;
    }
    if(alpha==90&&w==h)
    {
        pr("%.10lf
",w*h);
        return 0;
    }
    line line1[10];
    point p1={-w/2,h/2};
    point p2={w/2,h/2};
    point p3={w/2,-h/2};
    point p4={-w/2,-h/2};
    line1[1]={p1,p2};
    line1[2]={p2,p3};
    line1[3]={p3,p4};
    line1[4]={p4,p1};

    line line2[10];
    p1=rotate(p1,alpha);
    p2=rotate(p2,alpha);
    p3=rotate(p3,alpha);
    p4=rotate(p4,alpha);
    line2[1]={p1,p2};
    line2[2]={p2,p3};
    line2[3]={p3,p4};
    line2[4]={p4,p1};

    int cp=0;
    for(int i=1;i<=4;++i)
    {
        for(int j=1;j<=4;++j)
        {
            if(isIntersected(line1[i].a,line1[i].b,line2[j].a,line2[j].b))
                Pin[++cp]=intersection(line1[i].a,line1[i].b,line2[j].a,line2[j].b);
        }
    }
//    for(int i=1;i<=cp;++i)pr("%lf	%lf
",Pin[i].x,Pin[i].y);
    Graham(cp,Pin);
    pr("%.10lf
",getArea());
    return 0;
}

/**************************************************************************************/