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 :_rabbit
Created Time :2014/5/4 15:03:55
File Name :20.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
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)<eps)return 0;
return 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<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
double Length(Point a){
return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
Point vecunit(Point a){
return a/Length(a);
}
Point Normal(Point a){
return Point(-a.y,a.x)/Length(a);
}
Point Rotate(Point a,double rad){
return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
double Area2(Point a,Point b,Point c){
return Length(Cross(b-a,c-a));
}
struct Line{
Point p,v;
double ang;
Line(){};
Line(Point p,Point v):p(p),v(v){
ang=atan2(v.y,v.x);
}
bool operator < (const Line &L) const {
return ang<L.ang;
}
};
bool OnLeft(const Line &L,const Point &p){
return dcmp(Cross(L.v,p-L.p))>=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<Point> HPI(vector<Line> L){
int n=L.size();
sort(L.begin(),L.end());//将全部半平面依照極角排序。
int first,last;
vector<Point> p(n);
vector<Line> q(n);
vector<Point> ans;
q[first=last=0]=L[0];
for(int i=1;i<n;i++){
while(first<last&&!OnLeft(L[i],p[last-1]))last--;//删除頂部的半平面
while(first<last&&!OnLeft(L[i],p[first]))first++;//删除底部的半平面
q[++last]=L[i];//将目前的半平面假如雙端隊列頂部。
if(fabs(Cross(q[last].v,q[last-1].v))<eps){//對于極角同樣的，選擇性保留一個。
last--;
if(OnLeft(q[last],L[i].p))q[last]=L[i];
}
if(first<last)p[last-1]=GetLineIntersection(q[last-1],q[last]);//計算隊列頂部半平面交點。
}
while(first<last&&!OnLeft(q[first],p[last-1]))last--;//删除隊列頂部的無用半平面。
//cout<<first<<" "<<last<<endl;
if(last-first<=1)return ans;//半平面退化
p[last]=GetLineIntersection(q[last],q[first]);//計算隊列頂部與首部的交點。
for(int i=first;i<=last;i++)ans.push_back(p[i]);//将隊列中的點複制。
return ans;
}
double PolyArea(vector<Point> p){
int n=p.size();
double ans=0;
for(int i=1;i<n-1;i++)
ans+=Cross(p[i]-p[0],p[i+1]-p[0]);
return ans/2;
}
vector<Point> 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<n;i++)scanf("%lf%lf",&pp.x,&pp.y),p1.push_back(pp);
for(int i=0;i<m;i++)scanf("%lf%lf",&pp.x,&pp.y),p2.push_back(pp);
double ret1,ret2,ret=0;
ret1=PolyArea(p1);if(dcmp(ret1)<0)reverse(p1.begin(),p1.end());ret+=fabs(ret1);
ret2=PolyArea(p2);if(dcmp(ret2)<0)reverse(p2.begin(),p2.end());ret+=fabs(ret2);
for(int i=1;i<n-1;i++)
for(int j=1;j<m-1;j++){
vector<Point> 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<Line> 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<Point> tt=HPI(L);
if(flag1==flag2)ret-=PolyArea(tt);
else ret+=PolyArea(tt);
}
printf("%.2lf\n",ret);
}
return 0;
}