codeforces281CRectangle Puzzle+矩形旋轉+面積交

Description

You are given two rectangles on a plane. The centers of both rectangles are located in the origin of coordinates (meaning the center of the rectangle’s symmetry). The first rectangle’s sides are parallel to the coordinate axes: the length of the side that is parallel to the Ox axis, equals w, the length of the side that is parallel to the Oy axis, equals h. The second rectangle can be obtained by rotating the first rectangle relative to the origin of coordinates by angle α.

Your task is to find the area of the region which belongs to both given rectangles. This region is shaded in the picture.

Input

The first line contains three integers w, h, α (1 ≤ w, h ≤ 106; 0 ≤ α ≤ 180). Angle α is given in degrees.

Output

In a single line print a real number — the area of the region which belongs to both given rectangles.

The answer will be considered correct if its relative or absolute error doesn’t exceed 10 - 6.

Sample Input

Input

1 1 45

Output

0.828427125

Input

6 4 30

Output

19.668384925

Hint

The second sample has been drawn on the picture above.

弱菜表示什麼都不會，看了qscqesze的題解，，然并卵！寥寥幾行代碼。。什麼國小數學。我不造啊！

轉眼想了一下，就是關于原點旋轉嘛，，全部點都旋轉一下好了。就得到了新的矩形，然後多邊形面積交一下就好了。。。

好了不說。直接把自己模闆摳出來一貼，完了。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<set>

using namespace std;

const int maxn=;
const int maxisn=;
const double eps=;
const double pi=acos(-);

int dcmp(double x){
    if(x>eps) return ;
    return x<-eps ? - : ;
}
inline double Sqr(double x){
    return x*x;
}
struct Point{
    double x,y;
    Point(){x=y=;}
    Point(double x,double y):x(x),y(y){};
    friend Point operator + (const Point &a,const Point &b) {
        return Point(a.x+b.x,a.y+b.y);
    }
    friend Point operator - (const Point &a,const Point &b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    friend bool operator == (const Point &a,const Point &b) {
        return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
    }
    friend Point operator * (const Point &a,const double &b) {
        return Point(a.x*b,a.y*b);
    }
    friend Point operator * (const double &a,const Point &b) {
        return Point(a*b.x,a*b.y);
    }
    friend Point operator / (const Point &a,const double &b) {
        return Point(a.x/b,a.y/b);
    }
    friend bool operator < (const Point &a, const Point &b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
    inline double dot(const Point &b)const{
        return x*b.x+y*b.y;
    }
    inline double cross(const Point &b,const Point &c)const{
        return (b.x-x)*(c.y-y)-(c.x-x)*(b.y-y);
    }

};
Point LineCross(const Point &a,const Point &b,const Point &c,const Point &d){
    double u=a.cross(b,c),v=b.cross(a,d);
    return Point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));
}
double PolygonArea(Point p[],int n){
     if(n<) return ;
     double s=p[].y*(p[n-].x-p[].x);
     p[n]=p[];
     for(int i=;i<n;i++){
        s+=p[i].y*(p[i-].x-p[i+].x);
     }
     return fabs(s*);
}
double CPIA(Point a[],Point b[],int na,int nb){
    Point p[maxisn],temp[maxisn];
    int i,j,tn,sflag,eflag;
    a[na]=a[],b[nb]=b[];
    memcpy(p,b,sizeof(Point)*(nb+));
    for(i=;i<na&&nb>;++i){
        sflag=dcmp(a[i].cross(a[i+],p[]));
        for(j=tn=;j<nb;++j,sflag=eflag){
            if(sflag>=) temp[tn++]=p[j];
            eflag=dcmp(a[i].cross(a[i+],p[j+]));
            if((sflag^eflag)==-)
                temp[tn++]=LineCross(a[i],a[i+],p[j],p[j+]);
        }
        memcpy(p,temp,sizeof(Point)*tn);
        nb=tn,p[nb]=p[];
    }
    if(nb<) return ;
    return PolygonArea(p,nb);
}
double SPIA(Point a[],Point b[],int na,int nb){
    int i,j;
    Point t1[],t2[];
    double res=,if_clock_t1,if_clock_t2;
    a[na]=t1[]=a[];
    b[nb]=t2[]=b[];
    for(i=;i<na;i++){
        t1[]=a[i-],t1[]=a[i];
        if_clock_t1=dcmp(t1[].cross(t1[],t1[]));
        if(if_clock_t1<) swap(t1[],t1[]);
        for(j=;j<nb;j++){
            t2[]=b[j-],t2[]=b[j];
            if_clock_t2=dcmp(t2[].cross(t2[],t2[]));
            if(if_clock_t2<) swap(t2[],t2[]);
            res+=CPIA(t1,t2,,)*if_clock_t1*if_clock_t2;
        }
    }
    return res;//面積交
    //return PolygonArea(a,na)+PolygonArea(b,nb)-res;//面積并
}

//op沿遠點逆時針旋轉角度A//A*pi/180
Point rotate_point(const Point &p,double A) {
    double tx=p.x,ty=p.y;
    return Point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}

Point a[],b[];

int main(){
    double w,h,A;
    while(cin>>w>>h>>A){
        w=w*;
        h=h*;
        a[].x=w,a[].y=h;
        a[].x=-w,a[].y=h;
        a[].x=-w,a[].y=-h;
        a[].x=w,a[].y=-h;
        b[]=rotate_point(a[],A*pi/);
        b[]=rotate_point(a[],A*pi/);
        b[]=rotate_point(a[],A*pi/);
        b[]=rotate_point(a[],A*pi/);
        printf("%.9f\n",SPIA(a,b,,));
    }
    return ;
}