1376.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1376 on 2006-01-11 at 13:22:35 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 3200;
const double eps = 2e-6;

class Line {
public:
	int x1, y1, x2, y2, dx, dy;
	void make();
	bool operator !=(const Line&) const;
};
void Line::make() {
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	dx = x2 - x1; dy = y2 - y1;
	if(x1 == x2) dy = abs(dy);
	if(y1 == y2) dx = abs(dx);
}
bool Line::operator !=(const Line& l) const {
	return dy*l.dx != dx*l.dy;
}

class Point {
public:
	double x, y;
	void set(const Line&, const Line&);
	bool operator <(const Point&) const;
	bool operator !=(const Point&) const;
};
void Point::set(const Line& l1, const Line& l2) {
	double d = l1.dy*l2.dx - l2.dy*l1.dx;
	double k1 = l1.dy*l2.dx/d, k2 = l2.dy*l1.dx/d, k3 = l1.dx*l2.dx/d, k4 = l1.dy*l2.dy/d;
	x = k1*l1.x1 - k2*l2.x1 + k3*(l2.y1-l1.y1);
	y = k1*l2.y1 - k2*l1.y1 - k4*(l2.x1-l1.x1);
}
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);
}

int main()
{
	Line l[MAX];
	Point p[MAX];
	int i, j, k, n;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) l[i].make();
		int pln = 1;
		for(i = 0; i < n; i++) {
			pln++;
			int prev = -1, pn = 0;
			for(j = 0; j < i; j++) 
				if(l[i] != l[j]) p[pn++].set(l[i], l[j]);
			sort(p, p+pn);
			for(k = 0; k < pn; k++)
				if(prev == -1 || p[k] != p[prev]) prev = k, pln++;
		}
		printf("%d\n", pln);
	}
	
	return 0;
}