学步园

题目链接：Jack Straws

题意：二维坐标系上有好多线段，两条线段有交点就联通。根据输入求两条线段是否联通。

题解：用到二维向量+直线交点+点在线段上模板。并查集标记或者暴力都可以。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const double EPS = 1e-10;
double add( double a, double b){
	if( abs(a+b) < EPS * ( abs(a) + abs(b))) return 0;
	return a+b;
}
struct P{
	double x, y;
	int num;
	P() {}
	P(double x, double y) : x(x), y(y) {}
	P operator + (P p){ return P(add(x, p.x), add(y, p.y));}
	P operator - (P p){ return P(add(x, -p.x), add(y, -p.y));}
	P operator * (double d){ return P(x*d, y*d);}
	bool operator < (const P& a) const {
		if( x != a.x) return x < a.x;
		else return y < a.y;
	}
	double dot(P p){ return add(x*p.x, y*p.y);}
	double det(P p) { return add( x*p.y, -y*p.x);}
};

//点q是否在线段 p1--p2 上 
bool on_seg(P p1, P p2, P q){
	return (p1 - q).det(p2 - q) == 0 && (p1 - q ).dot(p2 - q) <= 0;
}
//line p1->p2     line q1->q2
P intersection(P p1, P p2, P q1, P q2){
	return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}
struct segment{
	P p1, p2;
}seg[20];
int f[200];
int getSet(int x){
	return f[x] = x == f[x] ? x : getSet(f[x]);
}
int mergSet(int x, int y){
	x = getSet(x);
	y = getSet(y);
	if( x > y ) swap(x, y);
	f[y] = x;
}
int main(){
	#ifndef in
	ios::sync_with_stdio(false);
	#endif
	int n;
	while(cin >> n){
		if( n == 0) break;
		for(int i = 1; i <= n; i ++) {
			cin >> seg[i].p1.x >> seg[i].p1.y >> seg[i].p2.x >> seg[i].p2.y;
		}
		for(int i = 1; i <= n+5; i ++) f[i] = i;
		for(int i = 1; i <= n; i ++){
			for(int j = 1; j < i; j ++){
				//一开始没有判平行，平行很重要。 
				if(( seg[i].p1 - seg[i].p2).det(seg[j].p1 - seg[j].p2) == 0){
					if( on_seg( seg[i].p1, seg[i].p2, seg[j].p1) 
						||  on_seg( seg[j].p1, seg[j].p2, seg[i].p1)
						||	on_seg( seg[i].p1, seg[i].p2, seg[j].p2)
						||	on_seg( seg[j].p1, seg[j].p2, seg[i].p2)){
						mergSet(i, j);
					}
				}
				else {
					P sec = intersection(seg[i].p1, seg[i].p2, seg[j].p1, seg[j].p2);
					if( on_seg( seg[i].p1, seg[i].p2, sec) && on_seg( seg[j].p1, seg[j].p2, sec)){
						mergSet(i, j);
					}
				}
			}
		}
		int x, y;
		while(1){
			cin >> x >> y;
			if( (x|y) == 0) break;
			if( getSet(x) == getSet(y) ) cout << "CONNECTED" << endl;
			else cout << "NOT CONNECTED" << endl; 
		}
	}
	return 0;
}