poj1279——求半平面交後凸多邊形的面積

題目連結：http://poj.org/problem?id=1279

The art galleries of the new and very futuristic building of the Center for Balkan Cooperation have the form of polygons (not necessarily convex). When a big exhibition is organized, watching over all of the pictures is a big security concern. Your task is that for a given gallery to write a program which finds the surface of the area of the floor, from which each point on the walls of the gallery is visible. On the figure 1. a map of a gallery is given in some co-ordinate system. The area wanted is shaded on the figure 2.

Input

The number of tasks T that your program have to solve will be on the first row of the input file. Input data for each task start with an integer N, 5 <= N <= 1500. Each of the next N rows of the input will contain the co-ordinates of a vertex of the polygon ? two integers that fit in 16-bit integer type, separated by a single space. Following the row with the co-ordinates of the last vertex for the task comes the line with the number of vertices for the next test and so on.

Output

For each test you must write on one line the required surface - a number with exactly two digits after the decimal point (the number should be rounded to the second digit after the decimal point).

Sample Input

1
7
0 0
4 4
4 7
9 7
13 -1
8 -6
4 -4      

Sample Output

80.00      

題目翻譯：

巴爾幹合作中心新式且極具未來感的建築的藝術畫廊具有多邊形（不一定是凸面）的形式。當一個大型展覽被組織時，觀看所有的圖檔是一個很大的安全問題。您的任務是，為給定的庫編寫一個程式，找到地闆區域的表面，從該圖庫的牆壁上的每個點可見。在圖1。在某種坐标系統中給出了一個庫的地圖。需要的區域在圖 2 上被蒙上。‎

‎輸入‎

‎程式必須解決的任務 T 數将位于輸入檔案的第一行上。每個任務的輸入資料以整數 N 開頭，5 <= N <= 1500。輸入的下一個 N 行将包含多邊形的頂點的坐标？兩個整數，适合 16 位整數類型，由單個空格分隔。與任務最後一個頂點的坐标的行之後，将出現一行下一個測試的頂點數，以因等。‎

‎輸出‎

‎對于每個測試，您必須在一行上寫入所需的曲面 - 小數點後正好有兩位數字的數字（數字應四舍五入到小數點後的第二個數字）。

半平面交+求凸包面積例題。

先求出半平面交後形成的凸包，然後用叉乘求出凸包面積。

關于半平面交的可以參考這個題（poj3335——半平面交模闆（方向不定）

#include<iostream>
#include<cmath> 
#include<algorithm>
using namespace std;
const double eps = 1e-8;
const int inf=0x3f3f3f3f;
struct Point{
    double x, y;
    Point(double x = 0, double y = 0):x(x),y(y){}
}p[1505];
int n;
typedef Point Vector;
Vector operator + (Vector A, Vector B){
    return Vector(A.x+B.x, A.y+B.y);
}
Vector operator - (Point A, Point B){
    return Vector(A.x-B.x, A.y-B.y);
}
Vector operator * (Vector A, double p){
    return Vector(A.x*p, A.y*p);
}
int sgn(double x){
    if(fabs(x) < eps)
        return 0;
    if(x < 0)
        return -1;
    return 1;
}
double Dot(Vector A, Vector B){
    return A.x*B.x + A.y*B.y;
}
double Cross(Vector A, Vector B){
    return A.x*B.y-A.y*B.x;
}
double Length(Vector A){
    return sqrt(Dot(A, A));
}
Vector Normal(Vector A){//向量A左轉90°的機關法向量
    double L = Length(A);
    return Vector(-A.y/L, A.x/L);
}
struct Line{
    Point p;//直線上任意一點
    Vector v;//方向向量，它的左邊就是對應的半平面
    double ang;//極角，即從x軸正半軸旋轉到向量v所需要的角（弧度）
    Line(){}
    Line(Point p, Vector v) : p(p), v(v){
        ang = atan2(v.y, v.x);
    }
    bool operator < (const Line& L) const {//排序用的比較運算符
        return ang < L.ang;
    }
}l[1505];
//點p在有向直線L的左側
bool OnLeft(Line L, Point p){
    return Cross(L.v, p - L.p) >= 0;
}
//兩直線交點。假定交點唯一存在
Point GetIntersection(Line a, Line b){
    Vector u = a.p - b.p;
    double t = Cross(b.v, u)/Cross(a.v, b.v);
    return a.p + a.v*t;
}
//半平面交的主過程
void HalfplaneIntersection(Line* L, int n, Point* poly){
    sort(L, L + n);//按照極角排序
    int fst = 0, lst = 0;//雙端隊列的第一個元素和最後一個元素
    Point *P = new Point[n];//p[i] 為 q[i]與q[i + 1]的交點
    Line *q = new Line[n];//雙端隊列
    q[fst = lst = 0] = L[0];//初始化為隻有一個半平面L[0]
    for(int i = 1; i < n; ++i){
        while(fst < lst && !OnLeft(L[i], P[lst - 1])) --lst;
        while(fst < lst && !OnLeft(L[i], P[fst])) ++fst;
        q[++lst] = L[i];
        if(sgn(Cross(q[lst].v, q[lst - 1].v)) == 0){
            //兩向量平行且同向，取内側一個
            --lst;
            if(OnLeft(q[lst], L[i].p)) q[lst] = L[i];
        }
        if(fst < lst)
            P[lst - 1] = GetIntersection(q[lst - 1], q[lst]);
    }
    while(fst < lst && !OnLeft(q[fst], P[lst - 1])) --lst;
    //删除無用平面
    if(lst - fst <= 1){
    	//空集
    	printf("0.00\n");
    	return ;
	}
    P[lst] = GetIntersection(q[lst], q[fst]);//計算首尾兩個半平面的交點
    //從deque複制到輸出中
    int m = 0;
    for(int i = fst; i <= lst; ++i) poly[m++] = P[i];
    if(m<3) printf("0.00\n");
    else{
    	double s = 0;
		for(int i = 1; i < m-1; i++)
			s+=Cross((poly[i]-poly[0]),(poly[i+1]-poly[0]));
		s=fabs(s)/2;
		printf("%.2f\n",s);
	}
}
void init(Point *p, int n) {
	double s = 0;
	for(int i = 0; i < n; i++)
		s+=Cross((p[(i+1)%n]-p[i]),(p[(i+2)%n]-p[(i+1)%n]));
	if(sgn(s)>0) {
		for(int i = 0; i < n/2; i++)
			swap(p[i], p[n-i-1]);
	}
}
int main(){
	int T;
	scanf("%d",&T); 
	while(T--){
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		init(p,n);
		l[0]=Line(p[0],p[n-1]-p[0]); 
		for(int i=1;i<n;i++)
			l[i]=Line(p[i],p[i-1]-p[i]);
		HalfplaneIntersection(l,n,p);
	}
	return 0;
}