1127.c

北大ACM网站 1127题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1127

#include <stdio.h>

#define mul(x, y) ((x-x0)*(y1-y0)-(y-y0)*(x1-x0))
#define max(a, b) ((a)>(b)? (a): (b))
#define min(a, b) ((a)<(b)? (a): (b))

int multi(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3)
{
	return mul(x2, y2) * mul(x3, y3) <= 0;
}

int judge(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3)
{
	return	multi(x0, y0, x1, y1, x2, y2, x3, y3) &&
		multi(x2, y2, x3, y3, x0, y0, x1, y1) &&
		max(x0, x1) >= min(x2, x3) &&
		max(x2, x3) >= min(x0, x1) &&
		max(y0, y1) >= min(y2, y3) &&
		max(y2, y3) >= min(y0, y1);
}

int main(void)
{
	int n, i, j, k, l[12][4];
	int r[12][12];

	while (scanf("%d", &n), n)
	{
		for (i = 0; i < n; i++)
			scanf("%d%d%d%d", l[i], l[i]+1, l[i]+2, l[i]+3);
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				r[i][j] = judge(l[i][0], l[i][1], l[i][2], l[i][3], l[j][0], l[j][1], l[j][2], l[j][3]);
		for (k = 0; k < n; k++)
			for (i = 0; i < n; i++)
				for (j = 0; j < n; j++)
					if (r[i][k] && r[k][j])
						r[i][j] = 1;
		while (scanf("%d%d", &i, &j), i+j)
			puts(r[i-1][j-1]? "CONNECTED": "NOT CONNECTED");
	}

	return 0;
}