Hdu-2892 area 计算几何 圆与凸多边形面积交

题面

题意:有一个凸多边形岛屿,然后告诉你从高空(x,y,h)投下炸弹,爆炸半径r,飞机水平速度和重力加速度,问岛屿被炸了多少

题解:算出来岛屿落地位置,再利用圆与凸多边形面积交

 #include<bits/stdc++.h>

 #define inf 1000000000000

 #define M 100009

 #define eps 1e-12

 #define PI acos(-1.0)

 using namespace std;

 struct Point

 {

     double x,y;

     Point(){}

     Point(double xx,double yy){x=xx;y=yy;}

     Point operator -(Point s){return Point(x-s.x,y-s.y);}

     Point operator +(Point s){return Point(x+s.x,y+s.y);}

     double operator *(Point s){return x*s.x+y*s.y;}

     double operator ^(Point 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(Point a){return sqrt(a*a);}

 double dis(Point a,Point b){return len(b-a);}//两点之间的距离

 double cross(Point a,Point b,Point c)//叉乘

 {

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

 }

 double dot(Point a,Point b,Point c)//点乘

 {

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

 }

 int judge(Point a,Point b,Point 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 ;

     return ;

 }

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

 {

     Point 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)>&&dot(c,a,b)>)

         {

             double angle1=*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)) swap(b,c);//默认b在圆内

             if(fabs(dis(a,b))<eps) return 0.0;//ab距离为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)!=-)

     {

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

         int n;

         scanf("%d",&n);

         for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);

         p[n+]=p[];

         double V=sqrt(**h);

         double t0=V/;

         double x0=x+x1*t0;

         double y0=y+y1*t0;

         Point O(x0,y0);

         for(int i=;i<=n+;i++) p[i]=p[i]-O;

         O=Point(,);

         double sum=;

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

         {

             int j=i+;

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

             if(cross(O,p[i],p[j])>) sum+=s; else sum-=s;

         }

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

     }

     return ;

 }