1890.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1890 on 2006-02-23 at 21:39:41 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 320;
const double eps = 1e-6;

class Point {
public:
	double x, y;
	bool operator <(const Point&) const;
	bool operator !=(const Point&) const;
};
bool Point::operator <(const Point& p) const {
	if(fabs(x-p.x) > eps) return x < p.x;
	else return y < p.y;
}
bool Point::operator !=(const Point& p) const {
	return fabs(x-p.x) > eps || fabs(y-p.y) > eps;
}

Point ins[MAX], p[MAX];
int in;

void draw(int, int);

int main()
{
	int n, t, i, j;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		int total = 1;
		for(i = 0; i < n; i++) {
			scanf("%lf %lf", &p[i].x, &p[i].y);
			if(i == 0) continue;
			ins[0] = p[i-1];
			for(in = j = 1; j < i-1; j++) 
				draw(j, i);
			sort(ins, ins+in);
			for(j = 1; j < in; j++)
				if(ins[j] != ins[j-1]) total++;
		}
		printf("Case %d: There are %d pieces.\n", t, total);
	}
	
	return 0;
}

void draw(int oa, int ob)
{
	double A1 = p[oa].y-p[oa-1].y, A2 = p[ob].y-p[ob-1].y;
	double B1 = p[oa].x-p[oa-1].x, B2 = p[ob].x-p[ob-1].x;
	double C1 = A1*p[oa].x-B1*p[oa].y, C2 = A2*p[ob].x-B2*p[ob].y;
	if(fabs(A1*B2-A2*B1) < eps) return;
	double x = (C1*B2-C2*B1)/(A1*B2-A2*B1), y = -(A1*C2-A2*C1)/(A1*B2-A2*B1);
	if(min(p[oa].x, p[oa-1].x)-x > eps || x-max(p[oa].x, p[oa-1].x) > eps) return;
	if(min(p[oa].y, p[oa-1].y)-y > eps || y-max(p[oa].y, p[oa-1].y) > eps) return;
	if(min(p[ob].x, p[ob-1].x)-x > eps || x-max(p[ob].x, p[ob-1].x) > eps) return;
	if(min(p[ob].y, p[ob-1].y)-y > eps || y-max(p[ob].y, p[ob-1].y) > eps) return;
	ins[in].x = x; ins[in].y = y; in++;
}