1102.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1102 on 2005-12-14 at 17:17:50 */ 
#include <cstdio>
#include <cstring>

const int MAX = 16;

class UFSet {
private:
	int parent[MAX];
public:
	void makeSet();
	int find(int);
	void unionSet(int, int);
};
void UFSet::makeSet() {
	memset(parent, -1, sizeof(parent));
}
int UFSet::find(int x) {
	if(parent[x] == -1) {
		return x;
	} else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x);
	int pY = find(y);
	if(pX != pY) {
		parent[pX] = pY;
	}
}

class Stick {
private:
	class Point {
	public:
		int x, y;
	};
	int min(int x, int y) const {
		return x < y ? x : y;
	}
	int max(int x, int y) const {
		return x > y ? x : y;
	}
public:
	Point b, e;
	void scan();
	bool covered(const Stick&) const;
};
void Stick::scan() {
	scanf("%d %d %d %d", &b.x, &b.y, &e.x, &e.y);
}
bool Stick::covered(const Stick& s) const {
	if(min(e.x, b.x) > max(s.e.x, s.b.x)) {
		return false;
	} else if(min(s.e.x, s.b.x) > max(e.x, b.x)) {
		return false;
	} else if(min(e.y, b.y) > max(s.e.y, s.b.y)) {
		return false;
	} else if(min(s.e.y, s.b.y) > max(e.y, b.y)) {
		return false;
	} else {
		int a = (s.b.y-e.y)*(b.x-e.x)-(b.y-e.y)*(s.b.x-e.x);
		int p = (s.e.y-e.y)*(b.x-e.x)-(b.y-e.y)*(s.e.x-e.x);
		int c = (b.y-s.e.y)*(s.b.x-s.e.x)-(s.b.y-s.e.y)*(b.x-s.e.x);
		int d = (e.y-s.e.y)*(s.b.x-s.e.x)-(s.b.y-s.e.y)*(e.x-s.e.x);
		return (a * p <= 0 && c * d <= 0);
	}
}

int main()
{
	UFSet ufs;
	Stick stick[MAX];
	int n, i, j;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		ufs.makeSet();
		for(i = 0; i < n; i++) {
			stick[i].scan();
		}
		for(i = 0; i < n; i++) {
			for(j = i+1; j < n; j++) {
				if(stick[i].covered(stick[j])) {
					ufs.unionSet(i, j);
				}
			}
		}
		int a, b;
		while(scanf("%d %d", &a, &b) != EOF && a*b != 0) {
			if(ufs.find(a-1) == ufs.find(b-1)) {
				printf("CONNECTED\n");
			} else {
				printf("NOT CONNECTED\n");
			}
		}
	}
	
	return 0;
}