Code: Select all
//SCUD Busters - acm.uva.es/p/v1/109.html
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#define REP(i,n) for(int tn = n, i = 0; i < tn; ++i)
#define FOR(i,a,b) for(int i = (a),tb = (b);i <= tb; ++i)
#define FORD(i,a,b) for(int i = (a),tb = (b);i >= tb; --i)
#define INF INT_MAX
#define MAXK 22
#define MAXP 102
typedef long LL;
using namespace std;
struct Point {
Point(){}
Point(LL x, LL y):x(x),y(y) {}
LL x,y;
}kng[MAXK][MAXP];
LL N,x,y,i,nk=0,np[MAXK];
double area[MAXK];
bool destroyed[MAXK];
vector<Point> hull;
bool operator==(const Point &a, const Point &b) { return 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); }
LL operator^(const Point &a, const Point &b) { return a.x*b.y - b.x*a.y; }
bool compareCoordinates(const Point &a, const Point &b) {
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
bool comparePolarAngles(const Point &a, const Point &b) {
Point a1 = a-kng[nk][0], b1 = b-kng[nk][0];
double
ma = a1.x != 0 ? double(a1.y)/a1.x : INT_MAX,
mb = b1.x != 0 ? double(b1.y)/b1.x : INT_MAX;
if(ma < 0 && mb < 0)return -ma < -mb;
if(ma < 0)return 0;
if(mb < 0)return 1;
return ma < mb;
}
bool isInside(Point a, int n)
{
int i, j, c = 0;
for (i = 0, j = np[n]-1; i < np[n]; j = i++) {
if ((((kng[n][i].y <= a.y) && (y < kng[n][j].y)) ||
((kng[n][j].y <= y) && (y < kng[n][i].y))) &&
(x < (kng[n][j].x - kng[n][i].x) * (y - kng[n][i].y) / (kng[n][j].y - kng[n][i].y) + kng[n][i].x))
c = !c;
}
return c;
}
double findPolygonArea(){
int res = 0;
REP(i,hull.size()) res += hull[i]^hull[(i+1)%hull.size()];
if(res<0)res = - res;
return res*0.5;
}
void findConvexHull() {
int nh=0;
sort(&kng[nk][0], &kng[nk][N],compareCoordinates);
sort(&kng[nk][1], &kng[nk][N], comparePolarAngles);
reverse(&kng[nk][0], &kng[nk][N]);
hull.clear();
hull.push_back(kng[nk][0]); nh++;
FOR(i,1,N-1){
Point p = kng[nk][i];
while(nh >= 2 && ((p-hull[nh-2])^(p-hull[nh-1])) >= 0) { hull.pop_back(); nh--;}
hull.push_back(p); nh++;
}
area[nk] = findPolygonArea();
np[nk] = hull.size();
REP(i, hull.size()) kng[nk][i] = hull[i];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
memset(kng, 0, sizeof(kng));
memset(np, 0, sizeof(np));
memset(area,0, sizeof(area));
memset(destroyed, 0, sizeof(destroyed));
while(1) {
scanf("%d", &N);
if(N == -1)break;
np[nk] = N;
REP(i,N) scanf("%d %d",&kng[nk][i].x, &kng[nk][i].y);
findConvexHull();
nk++;
}
while(scanf("%d %d", &x, &y) == 2){
REP(i, nk)
if(isInside(Point(x,y), i))
destroyed[i] = 1;
}
double ret = 0.0;
REP(i,nk) ret += destroyed[i] ? (double)area[i] : 0.0;
printf("%.2f\n", ret);
}
). Just to let you know because I really missed this small piece of information. Should anyone wish I can post it here but it was designed to spare memory resourses and CPU cycles (professional deformation 
) instead of being readable. It contains no comments (except the ones at my auxilary sheet of paper), I used funny and slang variable names in my native language etc. I can hint that I didn't use any float (or even double) variables (only int's and occasioanly long ints, you never know if the test system uses some old 16-bit integers) except till the very end when I needed to apply the half of the area formula. No other functions like sin, cos, tan, sqrt or their inverses, only +, - and *. Oh yes, understanding the cross product is an efficient weapon....
