poj1127（计算几何，并查集）

/*
translation:
    给出n根木棍的端点位置，然后问任意两个木棍是否连通
solution:
    计算几何，并查集
    首先计算出任意两个木棍之间是否有公共端点，如果有，就对两个木棍的编号进行并查集的unite操作。
    这样到最后只需要判断根节点是否相同即可。
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;
const int maxn = 20;
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;
    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);
    }
    double dot(P p) {    //内积
        return add(x * p.x, y * p.y);
    }
    double det(P p) {   //外积
        return add(x * p.y, -y * p.x);
    }
};

int par[maxn], high[maxn], n;
P p[maxn], q[maxn];

bool on_seg(P p1, P p2, P q)
{
    return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0;
}

P intersection(P p1, P p2, P q1, P q2)
{
    return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}

int get_root(int x)
{
    return par[x] == x ? x : par[x] = get_root(par[x]);
}

void unite(int x, int y)
{
    x = get_root(x);
    y = get_root(y);
    if(x == y)  return;
    //printf("unite %d %d\n", x, y);

    if(high[x] < high[y])   par[x] = y;
    else {
        par[y] = x;
        if(high[x] == high[y])  high[x]++;
    }
}

inline bool same(int x, int y)
{
    return get_root(x) == get_root(y);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n) && n) {
        for(int i = 0; i < maxn; i++) {
            par[i] = i;
            high[i] = 0;
        }

        for(int i = 1; i <= n; i++) {
            cin >> p[i].x >> p[i].y >> q[i].x >> q[i].y;
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                if((p[i] - q[i]).det(p[j] - q[j]) == 0) {
                    if(on_seg(p[i], q[i], p[j]) || on_seg(p[i], q[i], q[j]) ||
                       on_seg(p[j], q[j], p[i]) || on_seg(p[j], q[j], q[i])) {
                        unite(i, j);
                    }
                } else {
                    P tmp = intersection(p[i], q[i], p[j], q[j]);
                    if(on_seg(p[i], q[i], tmp) && on_seg(p[j], q[j], tmp)) {
                        unite(i, j);
                    }
                }
            }
        }

        int x, y;
        for(;;) {
            scanf("%d%d", &x, &y);
            if(x + y == 0)  break;

            if(get_root(x) == get_root(y))  printf("CONNECTED\n");
            else                            printf("NOT CONNECTED\n");
        }
    }
    return 0;
}