程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3060 多邊形面積並

HDU 3060 多邊形面積並

編輯：C++入門知識

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

Sample Output

1.75

給定兩個多邊形，求面積並

把多邊形分解成三角形，然後計算三角形的有向面積交。

代碼：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/4 15:03:55
File 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;
}