// @BEGIN_OF_SOURCE_CODE /* @JUDGE_ID: 17243NT 137 C++ "Andrew's Algorithm for Convex Hull" */ // Send to judge@uva.es #include #include #include #ifdef ONLINE_JUDGE #define ins cin #define outs cout #else #define ins fin #define outs fout ifstream fin("myprog.in"); ofstream fout("myprog.out"); #endif #define MAXPOLY 1000 #define ERROR 0.00000001 #define less(a, b) ((b - a) > ERROR) #define equal(a, b) (-ERROR < (b - a) && (b - a) < ERROR) typedef struct { double x; double y; } Point; int ccw(Point p0, Point p1, Point p2); int gethull(Point P[], int n, Point H[]); void insertpt(Point P, Point V[], int &n); int insidepoly(Point P, Point V[], int n); bool intersect(Point l1p1, Point l1p2, Point l2p1, Point l2p2); Point intersection(Point l1p1, Point l1p2, Point l2p1, Point l2p2); double isLeft(Point P0, Point P1, Point P2); double polyarea(int n, Point V[]); void sort(Point a[], int n); double xorarea(Point p1[], int n1, Point p2[], int n2); int ccw(Point p0, Point p1, Point p2) { double dx1, dx2, dy1, dy2; dx1 = p1.x - p0.x; dy1 = p1.y - p0.y; dx2 = p2.x - p0.x; dy2 = p2.y - p0.y; if(less(dy1 * dx2, dx1 * dy2)) return 1; if(less(dx1 * dy2, dy1 * dx2)) return -1; if(less(dx1 * dx2, 0) || less(dy1 * dy2, 0)) return -1; if(less(dx1 * dx1 + dy1 * dy1, dx2 * dx2 + dy2 * dy2)) return 1; return 0; } // Convex Hull is just used to orient the points int gethull(Point P[], int n, Point H[]) { int bot = 0, top = -1; int i; int minmin = 0, minmax; double xmin = P[0].x; for(i = 1; i < n; i++) if(P[i].x != xmin) break; minmax = i - 1; if(minmax == n - 1) { H[++top] = P[minmin]; if(P[minmax].y != P[minmin].y) H[++top] = P[minmax]; return top + 1; } int maxmin, maxmax = n - 1; double xmax = P[n - 1].x; for(i = n - 2; i >= 0; i--) if(P[i].x != xmax) break; maxmin = i + 1; H[++top] = P[minmin]; i = minmax; while(++i <= maxmin) { if(isLeft(P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin) continue; while(top > 0) { if(isLeft(H[top - 1], H[top], P[i]) > 0) break; else top--; } H[++top] = P[i]; } if(maxmax != maxmin) H[++top] = P[maxmax]; bot = top; i = maxmin; while(--i >= minmax) { if(isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax) continue; while(top > bot) { if(isLeft(H[top - 1], H[top], P[i]) > 0) break; else top--; } H[++top] = P[i]; } if(minmax != minmin) H[++top] = P[minmin]; return top + 1; } void insertpt(Point P, Point V[], int &n) { int i; for(i = 0; i < n; i++) if(equal(P.x, V[i].x) && equal(P.y, V[i].y)) return; V[n++] = P; } int insidepoly(Point P, Point V[], int n) { int cn = 0; for(int i = 0; i < n; i++) { if((!less(P.y, V[i].y) && less(P.y, V[i + 1].y)) || (less(P.y, V[i].y) && !less(P.y, V[i + 1].y))) { double vt = (P.y - V[i].y) / (V[i + 1].y - V[i].y); if(less(P.x, V[i].x + vt * (V[i + 1].x - V[i].x))) ++cn; } } return (cn & 1); } bool intersect(Point l1p1, Point l1p2, Point l2p1, Point l2p2) { return ((ccw(l1p1, l1p2, l2p1) * ccw(l1p1, l1p2, l2p2)) <= 0) && ((ccw(l2p1, l2p2, l1p1) * ccw(l2p1, l2p2, l1p2)) <= 0); } Point intersection(Point l1p1, Point l1p2, Point l2p1, Point l2p2) { Point pt = {-1, -1}; double a = l1p1.y - l1p2.y; double b = l1p2.x - l1p1.x; double d = l2p1.y - l2p2.y; double e = l2p2.x - l2p1.x; if(equal(b * d, a * e)) return pt; double c = a * l1p1.x + b * l1p1.y; double f = d * l2p1.x + e * l2p1.y; pt.x = (c * e - b * f) / (a * e - b * d); pt.y = (c * d - a * f) / (b * d - a * e); return pt; } double isLeft(Point P0, Point P1, Point P2) { return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y); } double polyarea(int n, Point V[]) { double area = 0; int i; for(i = 0; i < n; i++) area += V[i].x * V[i + 1].y - V[i].y * V[i + 1].x; if(area < 0) area = -area; return area / 2.0; } void sort(Point a[], int n) { int i, j; Point t; for(i = 0; i < n - 1; i++) { int min = i; for(j = i + 1; j < n; j++) { if(a[j].x < a[min].x) { min = j; } else if(a[j].x == a[min].x && a[j].y < a[min].y) { min = j; } } t = a[i]; a[i] = a[min]; a[min] = t; } } double xorarea(Point p1[], int n1, Point p2[], int n2) { Point pint[MAXPOLY]; Point convex[MAXPOLY]; int n = 0; int i, j; double oa, ca = 0; p1[n1] = p1[0], p2[n2] = p2[0]; oa = polyarea(n1, p1) + polyarea(n2, p2); for(i = 0; i < n1; i++) if(insidepoly(p1[i], p2, n2)) insertpt(p1[i], pint, n); for(i = 0; i < n2; i++) if(insidepoly(p2[i], p1, n1)) insertpt(p2[i], pint, n); for(i = 0; i < n1; i++) for(j = 0; j < n2; j++) { // outs << "(" << p1[i].x << ", " << p1[i].y << ") -> " // << "(" << p1[i + 1].x << ", " << p1[i + 1].y << ") and " // << "(" << p2[j].x << ", " << p2[j].y << ") -> " // << "(" << p2[j + 1].x << ", " << p2[j + 1].y << ")\n"; if(intersect(p1[i], p1[i + 1], p2[j], p2[j + 1])) { Point pt; pt = intersection(p1[i], p1[i + 1], p2[j], p2[j + 1]); // outs << "Intersect at (" << pt.x << ", " // << pt.y << ")\n"; if(pt.x != -1) insertpt(pt, pint, n); } } if(n >= 3) { sort(pint, n); n = gethull(pint, n, convex) - 1; ca = polyarea(n, convex); } return (oa - 2 * ca); } int main() { Point p1[MAXPOLY], p2[MAXPOLY]; int n1, n2, i; while(ins >> n1) { if(n1 == 0) break; for(i = 0; i < n1; i++) ins >> p1[i].x >> p1[i].y; ins >> n2; for(i = 0; i < n2; i++) ins >> p2[i].x >> p2[i].y; xorarea(p1, n1, p2, n2); outs << setprecision(2) << setiosflags(ios::showpoint) << setiosflags(ios::fixed) << setw(8) << xorarea(p1, n1, p2, n2); } outs << endl; return 0; } // @END_OF_SOURCE_CODE