1700.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1700 on 2006-08-16 at 19:47:18 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 10240;
const double eps = 1e-5;
 
class Segment {
public:
	double x1, y1, x2, y2;
	double dx, dy, ddx, ddy;
	void make();
	double left() const { return fabs(dx) < eps ? y1 : x1; }
	double right() const { return fabs(dx) < eps ? y2 : x2; }
	bool operator <(const Segment&) const;
	bool operator ==(const Segment&) const;
};
void Segment::make() {
	scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
	if(x1 > x2 || (x1 == x2 && y1 > y2)) { swap(x1, x2); swap(y1, y2); }
	dx = x2-x1; dy = y2-y1; ddy = x2*y1-x1*y2;
	if(fabs(dx) < eps) ddy = abs(ddy);
}
bool Segment::operator <(const Segment& s) const {
	double k = dx*s.dy-dy*s.dx, d = dx*s.ddy-ddy*s.dx;
	if(fabs(k) > eps) return k < 0;
	else if(fabs(dx) < eps && fabs(x1-s.x1) > eps) return x1 < s.x1;
	else if(fabs(d) > eps) return d < 0;
	else if(fabs(dx) < eps) return y1 < s.y1;
	else return x1 < s.x1;
}
bool Segment::operator ==(const Segment& s) const {
	if(fabs(dx*s.dy-dy*s.dx) > eps) return false;
	else if(fabs(dx) < eps) return x1 == s.x1;
	else return fabs(dx*s.ddy-ddy*s.dx) < eps;
}

struct cmp {
	bool operator ()(const double d1, const double d2) const {
		return d2-d1 > eps;
	}
};

Segment s[N];
 
int main()
{
	int n;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(int i = 0; i < n; i++) s[i].make();
		sort(s, s+n);
		int line = 0;
		for(int i = 0, j = 0; i < n; i = j) {
			double r = -1e20;
			for(; j < n && s[i] == s[j]; j++) {
				if(s[j].left()-r > eps) { line++; r = -1e20; }
				r >?= s[j].right();
			}
		}
		printf("%d\n", line);
	}
	
	return 0;
}