2104.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2104 on 2006-04-14 at 06:34:38 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const double eps = 1e-8;

class Point {
public:
	double x, y;
	Point(double cx = 0, double cy = 0) : x(cx), y(cy) {}
	void make() { scanf("%lf %lf", &x, &y); }
	double dis(const Point&) const;
	bool equalTo(const Point&) const;
	bool operator <(const Point&) const;
};
double Point::dis(const Point& p) const {
	return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
}
bool Point::equalTo(const Point& p) const {
	return fabs(x-p.x) < eps && fabs(y-p.y) < eps;
}
bool Point::operator <(const Point& p) const {
	if(fabs(x-p.x) > eps) return x < p.x;
	else return y < p.y;
}

Point ins[MAX];
int in;

class Polygon {
private:
	Point v[MAX];
	int n;
public:
	void make(int);
	void cut(const Point&, const Point&) const;
	bool inside(const Point&) const;
};
void Polygon::make(int pn) {
	n = pn; int i;
	for(i = 0; i < n; i++) v[i].make();
}
void Polygon::cut(const Point& b, const Point& e) const {
	int i; in = 0;
	for(i = 0; i < n; i++) {
		int nxt = (i+1)%n;
		double dx1 = b.x-e.x, dy1 = b.y-e.y, dx2 = v[nxt].x-v[i].x, dy2 = v[nxt].y-v[i].y;
		if(fabs(dx1*dy2-dx2*dy1) < eps) continue;
		double ix, iy, k1 = dy1/dx1, k2 = dy2/dx2;
		if(fabs(dx1) < eps) ix = b.x, iy = k2*(ix-v[i].x)+v[i].y;
		else if(fabs(dx2) < eps) ix = v[i].x, iy = k1*(ix-b.x)+b.y;
		else {
			ix = (k2*v[i].x-v[i].y+b.y-k1*b.x) / (k2-k1);
			iy = k1*(ix-b.x)+b.y;
		}
		if(min(v[i].x, v[nxt].x)-ix > eps || ix-max(v[i].x, v[nxt].x) > eps) continue;
		if(min(v[i].y, v[nxt].y)-iy > eps || iy-max(v[i].y, v[nxt].y) > eps) continue;
		ins[in].x = ix; ins[in++].y = iy;
	}
}
bool Polygon::inside(const Point& p) const {
	bool inp = false; int i;
	for(i = 0; i < n; i++) {
		int nxt = (i+1)%n;
		if(fabs(v[i].dis(p)+v[nxt].dis(p)-v[i].dis(v[nxt])) < eps) return true;
		if (((v[i].y <= p.y && p.y < v[nxt].y) || (v[nxt].y <= p.y && p.y < v[i].y)) &&
			p.x < (v[nxt].x-v[i].x)*(p.y-v[i].y)/(v[nxt].y-v[i].y)+v[i].x) inp = !inp;
	}
	return inp;
}

int main()
{
	Polygon poly;
	int n, m, i, j;

	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		poly.make(n);
		for(i = 0; i < m; i++) {
			Point b, e; b.make(); e.make();
			poly.cut(b, e);
			sort(ins, ins+in);
			double len = 0;
			for(j = 1; j < in; j++) {
				double mx = (ins[j].x + ins[j-1].x) / 2, my = (ins[j].y + ins[j-1].y) / 2;
				if(poly.inside(Point(mx, my))) len += ins[j-1].dis(ins[j]);
			}
			printf("%.3lf\n", len);
		}
	}
	
	return 0;
}