2081.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2081 on 2005-10-28 at 21:42:40 */ 
#include <cstdio>

const int MAX = 100002;
const double eps = 1e-4;

class Point {
public:
	double x;
	double y;
};

class Stick {
public:
	Point b;
	Point e;
	bool covered(Stick &s) {
		double a = (s.b.y-e.y)*(b.x-e.x)-(b.y-e.y)*(s.b.x-e.x);
		double p = (s.e.y-e.y)*(b.x-e.x)-(b.y-e.y)*(s.e.x-e.x);
		double c = (b.y-s.e.y)*(s.b.x-s.e.x)-(s.b.y-s.e.y)*(b.x-s.e.x);
		double d = (e.y-s.e.y)*(s.b.x-s.e.x)-(s.b.y-s.e.y)*(e.x-s.e.x);
		if(a * p < eps && c * d < eps) {
			return true;
		} else {
			return false;
		}
	}
};

Stick stick[MAX];
int prev[MAX];
int next[MAX];

int main()
{
	int i, j;
	int n, limit;
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			limit = n + 1;
			next[0] = limit;
			prev[limit] = 0;
			for(i = 1; i <= n; i++) {
				scanf("%lf %lf %lf %lf", &stick[i].b.x, &stick[i].b.y, 
					&stick[i].e.x, &stick[i].e.y);
				for(j = next[0]; j != limit; j = next[j]) {
					if(stick[i].covered(stick[j])) {
						next[prev[j]] = next[j];
						prev[next[j]] = prev[j];
					}
				}
				next[i] = limit;
				prev[i] = prev[limit];
				prev[limit] = next[prev[limit]] = i;
			}
			printf("Top sticks:");
			for(i = next[0]; i != limit; i = next[i]) {
				printf(" %d", i);
				if(next[i] == limit) {
					putchar('.');
				} else {
					putchar(',');
				}
			}
			putchar('\n');
		}
	}
	
	return 0;
}