多角形と円の交差面積(テンプレート)hdu 2892、hdu 4404

area
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 686    Accepted Submission(s): 265
Problem Description
シロは最近空軍にパイロットとして特別招かれ、実戦演習に参加した.演習の内容はある島を爆撃することです..
優秀なパイロットとして、任務は必ず完成しなければならない.もちろん、シロの優れた操作で、順調に爆弾を島のどこかに投げたが、長官がもっと関心を持っているのは、シロが投げた爆弾が島のどのくらいの地域を破壊したのかということだ.
島は不規則な多角形であり、爆弾の爆発半径はRである.
シロは自分が(x,y,h)の空間座標で(x 1,y 1,0)の速度水平飛行中に投下した爆弾だけを知っています.シロが破壊した島の面積がどれだけ大きいか計算してください.重力加速度G=10.
 
Input
まず3つの数がシロの投弾を表す座標(x,y,h)を入力する.
次に、2つの数を入力して、飛行機の現在の速度(x 1,y 1)を表す.
次に爆弾の爆発半径Rを入力する.
島がn個の点からなることを表すnの数を入力します.
最後にn行を入力し、各行に(x',y')座標を入力し、島の頂点を表します(順勢針または反時計回りに与えられます).(3<= n < 100000)
 
Output
実際に爆撃された島の面積を表す2桁の小数点を出力します.
 
Sample Input
0 0 2000 100 0 100 4 1900 100 2000 100 2000 -100 1900 -100
 
Sample Output
15707.96

#include"cstdio"

#include"cstring"

#include"cstdlib"

#include"cmath"

#include"string"

#include"map"

#include"cstring"

#include"algorithm"

#include"iostream"

#include"set"

#include"queue"

#include"stack"

#define inf 1000000000000

#define M 100009

#define LL long long

#define eps 1e-12

#define mod 1000000007

#define PI acos(-1.0)

using namespace std;

struct node

{

    double x,y;

    node(){}

    node(double xx,double yy)

    {

        x=xx;

        y=yy;

    }

    node operator -(node s)

    {

        return node(x-s.x,y-s.y);

    }

    node operator +(node s)

    {

        return node(x+s.x,y+s.y);

    }

    double operator *(node s)

    {

        return x*s.x+y*s.y;

    }

    double operator ^(node s)

    {

        return x*s.y-y*s.x;

    }

}p[M];

double max(double a,double b)

{

    return a>b?a:b;

}

double min(double a,double b)

{

    return a<b?a:b;

}

double len(node a)

{

    return sqrt(a*a);

}

double dis(node a,node b)//       

{

    return len(b-a);

}

double cross(node a,node b,node c)//  

{

    return (b-a)^(c-a);

}

double dot(node a,node b,node c)//  

{

    return (b-a)*(c-a);

}

int judge(node a,node b,node c)//  c   ab   （   c   ab ）

{

    if(c.x>=min(a.x,b.x)

       &&c.x<=max(a.x,b.x)

       &&c.y>=min(a.y,b.y)

       &&c.y<=max(a.y,b.y))

        return 1;

    return 0;

}

double area(node b,node c,double r)

{

    node a(0.0,0.0);

    if(dis(b,c)<eps)

        return 0.0;

    double h=fabs(cross(a,b,c))/dis(b,c);

    if(dis(a,b)>r-eps&&dis(a,c)>r-eps)//                 

    {

        double angle=acos(dot(a,b,c)/dis(a,b)/dis(a,c));

        if(h>r-eps)

        {

            return 0.5*r*r*angle;

        }

        else if(dot(b,a,c)>0&&dot(c,a,b)>0)

        {

            double angle1=2*acos(h/r);

            return 0.5*r*r*fabs(angle-angle1)+0.5*r*r*sin(angle1);

        }

        else

        {

            return 0.5*r*r*angle;

        }

    }

    else if(dis(a,b)<r+eps&&dis(a,c)<r+eps)//           

    {

        return 0.5*fabs(cross(a,b,c));

    }

    else//                 

    {

        if(dis(a,b)>dis(a,c))//  b   

        {

            swap(b,c);

        }

        if(fabs(dis(a,b))<eps)//ab   0    0

        {

            return 0.0;

        }

        if(dot(b,a,c)<eps)

        {

            double angle1=acos(h/dis(a,b));

            double angle2=acos(h/r)-angle1;

            double angle3=acos(h/dis(a,c))-acos(h/r);

            return 0.5*dis(a,b)*r*sin(angle2)+0.5*r*r*angle3;



        }

        else

        {

            double angle1=acos(h/dis(a,b));

            double angle2=acos(h/r);

            double angle3=acos(h/dis(a,c))-angle2;

            return 0.5*r*dis(a,b)*sin(angle1+angle2)+0.5*r*r*angle3;

        }

    }

}

int main()

{

    double x,y,h,x1,y1,R;

    while(scanf("%lf%lf%lf",&x,&y,&h)!=-1)

    {

        scanf("%lf%lf%lf",&x1,&y1,&R);

        int n;

        scanf("%d",&n);

        for(int i=0;i<n;i++)

        {

            scanf("%lf%lf",&p[i].x,&p[i].y);

        }

        p[n]=p[0];

        double V=sqrt(2*10*h);

        double t0=V/10;

        double x0=x+x1*t0;

        double y0=y+y1*t0;

        node O(x0,y0);

        for(int i=0;i<=n;i++)

            p[i]=p[i]-O;

        O=node(0,0);

        double sum=0;

        for(int i=0;i<n;i++)

        {

            int j=i+1;

            double s=area(p[i],p[j],R);

            if(cross(O,p[i],p[j])>0)

                sum+=s;

            else

                sum-=s;

        }

        printf("%.2lf
",fabs(sum));

    }

    return 0;

}