## 2013年8月30日

### UVa 109 - SCUD Busters

Reference : http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html#6
#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct P {
bool operator<(const P & other) const {
return (x == other.x) ? (y < other.y) : (x < other.x);
}
int x, y;
};

typedef vector<P> Kingdom;

int cross(P o, P a, P b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

Kingdom convexHull(Kingdom & k) {
sort(k.begin(), k.end());
P CH[100];
int m = 0;
for (int i = 0; i < k.size(); i++) {
while (m >= 2 && cross(CH[m - 2], CH[m - 1], k[i]) <= 0) {
m--;
}
CH[m++] = k[i];
}
for (int i = k.size() - 2, t = m + 1; i >= 0; i--) {
while (m >= t && cross(CH[m - 2], CH[m - 1], k[i]) <= 0) {
m--;
}
CH[m++] = k[i];
}
return Kingdom(CH, CH + m);
}

int area(Kingdom & k) {
int sum = 0;
for(int i = 1; i < k.size(); i++) {
sum += (k[i - 1].x * k[i].y) - (k[i].x * k[i - 1].y);
}
return sum;
}

bool in(P p, Kingdom & k) {
int sum = area(k);
for (int i = 1; i < k.size() && sum >= 0; i++) {
Kingdom temp;
temp.PB(p);
temp.PB(k[i - 1]);
temp.PB(k[i]);
temp.PB(p);
int tempSum = area(temp);
if (tempSum < 0) {
return false;
}
sum -= tempSum;
}
return sum == 0;
}

int main() {
vector<Kingdom> v;
int n, x, y;
while (scanf("%d", &n) && n != -1) {
Kingdom k;
for (int i = 0; i < n; i++) {
scanf("%d%d", &x, &y);
k.PB((P){x, y});
}
v.PB(convexHull(k));
}
vector<bool> over(v.size(), false);
while (scanf("%d%d", &x, &y) == 2) {
for (int i = 0; i < v.size(); i++) {
if (!over[i]) {
over[i] = in((P){x, y}, v[i]);
}
}
}
int ans = 0;
for (int i = 0; i < v.size(); i++) {
if (over[i]) {
ans += area(v[i]);
}
}
printf("%.2lf\n", ans * 0.5);
return 0;
}