Polygons

Given two convex polygons, they may or may not overlap. If they do overlap, they will do so to differing degrees and in different ways. Write a program that will read in the coordinates of the corners of two convex polygons and calculate the `exclusive or' of the two areas, that is the area that is bounded by exactly one of the polygons. The desired area is shaded in the following diagram:

Input

Input will consist of pairs of lines each containing the number of vertices of the polygon, followed by that many pairs of integers representing the x,y coordinates of the corners in a clockwise direction. All the coordinates will be positive integers less than 100. For each pair of polygons (pair of lines in the data file), your program should print out the desired area correct to two decimal places. The input will end with a line containing a zero (0).

Output

Output will consist of a single line containing the desired area written as a succession of eight (8) digit fields with two (2) digits after the decimal point. There will not be enough cases to need more than one line.

Sample input

3  5 5  8 1  2 3
3  5 5  8 1  2 3
4  1 2  1 4  5 4  5 2
6  6 3  8 2  8 1  4 1  4 2  5 3
0

Sample output

0.00 13.50

where represents a single space.

---

題目描述：

給兩個凸多邊形，剔除共同區域後的總面積為何？

題目解法：

兩個凸多邊形的交集也一定是凸多邊形。

而半平面交寫起來有點麻煩，這裡考慮找到所有線段交點，
以及使用射線法找到一個點是否在另一個凸包內部。

把這些點找出來後，做一次凸包計算面積即可。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
};
struct Seg {
    Pt s, e;
};
int inInterval(Seg a, Pt p) {
    return
        min(a.s.x, a.e.x) <= p.x &&
        p.x <= max(a.s.x, a.e.x) &&
        min(a.s.y, a.e.y) <= p.y &&
        p.y <= max(a.s.y, a.e.y);
}
int calcIntersection(Seg a, Seg b, Pt &p) {
    double a1, b1, c1, a2, b2, c2;
    double D, Dx, Dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    D = a1*b2 - a2*b1;
    Dx = c1*b2 - c2*b1;
    Dy = a1*c2 - a2*c1;
    if(fabs(D) < eps) // NONE or LINE
        return 0;
    p.x = Dx/D, p.y = Dy/D;
    /*printf("%lf %lf - %lf %lf\n", a.s.x, a.s.y, a.e.x, a.e.y);
    printf("%lf %lf - %lf %lf\n", b.s.x, b.s.y, b.e.x, b.e.y);
    printf("%lf %lf\n", p.x, p.y);*/
    return inInterval(a, p) == 1 && inInterval(b, p) == 1;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double calcArea(Pt p[], int n) {
    if(n < 3)   return 0.0;
    double ret = 0;
    int i;
    p[n] = p[0];
    for(i = 0; i < n; i++)
        ret += p[i].x*p[i+1].y-p[i].y*p[i+1].x;
    return fabs(ret)/2;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m-1;
}
int main() {
    int n, m, o;
    int i, j, p, q;
    Pt a[1005], b[1005];
    Pt ta[1005], tb[1005];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            scanf("%lf %lf", &a[i].x, &a[i].y);
        scanf("%d", &m);
        for(i = 0; i < m; i++)
            scanf("%lf %lf", &b[i].x, &b[i].y);
        Seg s1, s2;
        Pt ret[1005], ch[1005];
        int retN = 0;
        for(i = 0, j = n-1; i < n; j = i++) {
            s1.s = a[i], s1.e = a[j];
            for(p = 0, q = m-1; p < m; q = p++) {
                s2.s = b[p], s2.e = b[q];
                if(calcIntersection(s1, s2, ret[retN])) {
                    retN++;
                    /*printf("%lf %lf - %lf %lf\n", s1.s.x, s1.s.y, s1.e.x, s1.e.y);
                    printf("%lf %lf - %lf %lf +++\n", s2.s.x, s2.s.y, s2.e.x, s2.e.y);*/
                }
            }
        }
        for(i = 0; i < n; i++)
            if(inPolygon(b, m, a[i]))
                ret[retN++] = a[i];
        for(i = 0; i < m; i++)
            if(inPolygon(a, n, b[i]))
                ret[retN++] = b[i];
        n = monotone(n, a, ta);
        m = monotone(m, b, tb);
        o = monotone(retN, ret, ch);
        double area = calcArea(ta, n)+calcArea(tb, m)-2*calcArea(ch, o);
        printf("%8.2lf", area);
    }
    puts("");
    return 0;
}