1157.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1157 on 2007-06-10 at 20:43:15 */
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 128;
const double eps = 1e-9;

class Point {	
public:
	double x, y;
	Point() {}
	Point(double tx, double ty) : x(tx), y(ty) {}
	int quadrant() const
		{ return x > -eps ? (y > -eps ? 0 : 3) : (y > -eps ? 1 : 2); }
	double distance(const Point& p) const
		{ return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)); }
	double abs() const { return sqrt(x*x+y*y); }
	bool operator ==(const Point& p) const
		{ return fabs(x-p.x) < eps && fabs(y-p.y) < eps; }
	bool operator !=(const Point& p) const { return !(*this == p); }
	Point operator -(const Point& p) const { return Point(x-p.x, y-p.y); }
	Point operator +(const Point& p) const { return Point(x+p.x, y+p.y); }
	double pmult(const Point& p) const { return x*p.x+y*p.y; }
	double xmult(const Point& p) const { return x*p.y-y*p.x; }
};

enum { INSIDE, ONEDGE, OUTSIDE };

class Polygon {
public:
	Point pt[N];
	int n;
public:
	Polygon() : n(0) {}
	void clear() { n = 0; }
	void insert(double x, double y) { pt[n++] = Point(x, y); }
	void insert(const Point& t) { pt[n++] = t; }
	double area() const;
	double perimeter() const;
	int position(const Point&) const;
//	double intersectedArea(const Polygon&) const;
};
double Polygon::area() const {
	double res = 0;
	for(int i = 0; i < n; i++)
		res += pt[i].xmult(pt[(i+1)%n])/2;
	return res;
}
double Polygon::perimeter() const {
	double res = 0;
	for(int i = 0; i < n; i++)
		res += pt[i].distance(pt[(i+1)%n]);
	return res;
}
int Polygon::position(const Point& p) const {
	for(int i = 0; i < n; i++)
		if(p == pt[i]) return ONEDGE;
	int sum = 0;
	for(int i = 0; i < n; i++) {
		Point a = pt[i]-p, b = pt[(i+1)%n]-p;
		double xmult = a.xmult(b);
		if(fabs(xmult) < eps && a.x*b.x <= eps && a.y*b.y <= eps) return ONEDGE;
		int pq = a.quadrant(), tq = b.quadrant();
		if(tq == pq) {}
		else if(tq == (pq+1)%4) sum++;
		else if(tq == (pq+3)%4) sum--;
		else if(xmult > eps) sum += 2;
		else sum -= 2;
	}
	return sum ? INSIDE : OUTSIDE;
}

class PointSet {
private:
	Point pt[N];
	int n;
public:
	PointSet() : n(0) {}
	void clear() { n = 0; }
	void insert(double x, double y) { pt[n++] = Point(x, y); }
	void insert(const Point& t) { pt[n++] = t; }
	Polygon convexHull() const;
};
bool ptcmp(const Point& p1, const Point& p2) {
	if(fabs(p1.y*p2.x-p2.y*p1.x) > eps) return p1.y*p2.x > p2.y*p1.x;
	else return p1.x*p1.x+p1.y*p1.y+eps > p2.x*p2.x+p2.y*p2.y;
}
Polygon PointSet::convexHull() const {
	Point pts[N];
	int id = 0;
	for(int i = 1; i < n; i++)
		if(pt[i].x < pt[id].x ||
			(fabs(pt[i].x-pt[id].x) < eps && pt[i].y < pt[id].y)) id = i;
	int tm = 0, m = 1;
	for(int i = 0; i < n; i++)
		if(pt[i] != pt[id]) pts[tm++] = pt[i]-pt[id];
	sort(pts, pts+tm, ptcmp);
	for(int i = 1; i < tm; i++)
		if(fabs(pts[i].xmult(pts[i-1])) > eps) pts[m++] = pts[i];
	vector<Point> stk;
	stk.push_back(pt[id]); stk.push_back(pts[0]+pt[id]);
	for(int i = 1; i < m; i++) {
		Point tp = pts[i]+pt[id];
		while(stk.size() >= 2) {
			Point v1 = stk.back()-stk[stk.size()-2], v2 = tp-stk.back();
			if(v1.xmult(v2) > -eps) stk.pop_back();
			else break;
		}
		stk.push_back(tp);
	}
	Polygon p;
	while(!stk.empty()) { p.insert(stk.back()); stk.pop_back(); }
	return p;
}

int main()
{
	Polygon kdm[N];
	int n, m;
	for(m = 0; scanf("%d", &n) != EOF && n != -1; m++) {
		PointSet pt; pt.clear();
		for(int i = 0; i < n; i++) {
			int a, b; scanf("%d %d", &a, &b);
			pt.insert(a, b);
		}
		kdm[m] = pt.convexHull();
	}
	bool d[N] = { false };
	double res = 0;
	int x, y;
	while(scanf("%d %d", &x, &y) != EOF)
		for(int i = 0; i < m; i++)
			if(!d[i] && kdm[i].position(Point(x, y)) == INSIDE) d[i] = true;
	for(int i = 0; i < m; i++)
		if(d[i]) res += fabs(kdm[i].area());
	printf("%.2lf\n", res);
	return 0;
}