Area2

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1197 Accepted Submission(s): 278

Problem Description

小白近期又被空军特招为飞行员，參与一项实战演习。演习的内容还是轰炸某个岛屿（这次的岛屿非常大，非常大非常大非常大，大到炸弹怎么扔都能全然在岛屿上引爆），看来小白确实是飞行员的命。。。

这一次，小白扔的炸弹比較奇怪，爆炸的覆盖区域不是圆形，而是一个不规则的简单多边形，请你再次帮助小白，计算出炸到了多少面积。

须要注意的是，这次小白一共扔了两枚炸弹，可是两枚炸弹炸到的公共部分的面积仅仅能计算一次。

Input

首先输入两个数n，m，分别代表两枚炸弹爆炸覆盖到的图形的顶点数；

接着输入n行，每行输入一个（x，y）坐标，代表第一枚炸弹爆炸范围图形的顶点（按顺势针或者逆时针给出）。

最后输入m行，每行输入一个（x'，y'）坐标，代表第二枚炸弹爆炸范围图形的顶点（按顺势针或者逆时针给出）。

(3<= n，m <= 500)

Output

输出一个两位小数，表示实际轰炸到的岛屿的面积。

Sample Input

       4 4 0 0 0 1 1 1 1 0 0.5 0.5 0.5 1.5 1.5 1.5 1.5 0.5 

Sample Output

       1.75 

给定两个多边形，求面积并

把多边形分解成三角形，然后计算三角形的有向面积交。

代码：

/* ***********************************************Author :_rabbitCreated Time :2014/5/4 15:03:55File Name :20.cpp************************************************ */#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  using namespace std;#define INF 10000000#define eps 1e-8#define pi acos(-1.0)typedef long long ll;int dcmp(double x){ if(fabs(x)
                   
                    0?1:-1; } struct Point{ double x,y; Point(double _x=0,double _y=0){ x=_x;y=_y; } }; Point operator + (const Point &a,const Point &b){ return Point(a.x+b.x,a.y+b.y); } Point operator - (const Point &a,const Point &b){ return Point(a.x-b.x,a.y-b.y); } Point operator * (const Point &a,const double &p){ return Point(a.x*p,a.y*p); } Point operator / (const Point &a,const double &p){ return Point(a.x/p,a.y/p); } bool operator < (const Point &a,const Point &b){ return a.x
                    
                     
                      =0; } Point GetLineIntersection(Point p,Point v,Point q,Point w){ Point u=p-q; double t=Cross(w,u)/Cross(v,w); return p+v*t; } Point GetLineIntersection(Line a,Line b){ return GetLineIntersection(a.p,a.v,b.p,b.v); } vector
                      
                        HPI(vector
                       
                         L){ int n=L.size(); sort(L.begin(),L.end());//将全部半平面依照极角排序。 int first,last; vector
                        
                          p(n); vector
                         
                           q(n); vector
                          
                            ans; q[first=last=0]=L[0]; for(int i=1;i
                           
                             p){ int n=p.size(); double ans=0; for(int i=1;i
                            
                              p1,p2;int main(){ //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int n,m; while(~scanf("%d%d",&n,&m)){ Point pp; p1.clear();p2.clear(); for(int i=0;i
                             
                               s1,s2; s1.push_back(p1[0]); s1.push_back(p1[i]); s1.push_back(p1[i+1]); s2.push_back(p2[0]); s2.push_back(p2[j]); s2.push_back(p2[j+1]); double r1,r2; int flag1,flag2; r1=PolyArea(s1); if(dcmp(r1)>=0)flag1=1;else flag1=0; if(dcmp(r1)<0)reverse(s1.begin(),s1.end()); r2=PolyArea(s2); if(dcmp(r2)>=0)flag2=1;else flag2=0; if(dcmp(r2)<0)reverse(s2.begin(),s2.end()); vector
                              
                                L; for(int k=0;k<3;k++) L.push_back(Line(s1[k],s1[(k+1)%3]-s1[k])); for(int k=0;k<3;k++) L.push_back(Line(s2[k],s2[(k+1)%3]-s2[k])); vector
                               
                                 tt=HPI(L); if(flag1==flag2)ret-=PolyArea(tt); else ret+=PolyArea(tt); } printf("%.2lf\n",ret); } return 0;}

转载地址：http://mrqll.baihongyu.com/

你可能感兴趣的文章