学步园

在搜计算几何的题目，网上看到一个说这个要计算几何+并查集，然后就去看了。看完发现题目本身很简单，而且感觉完全不用并查集，当然，如果后面的询问很多的话，可以用记忆化进行优化。总之，并查集是可以不用的。

判断两个线段相交的代码懒得写了，直接把判共线的一种情况用直线相交的模版来做了。

/*
 * Author: stormdpzh
 * Created Time:  2013/3/29 23:03:54
 * File Name: poj_1127.cpp
 */
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <functional>

#define sz(v) ((int)(v).size())
#define rep(i, n) for(int i = 0; i < n; i++)
#define repf(i, a, b) for(int i = a; i <= b; i++)
#define repd(i, a, b) for(int i = a; i >= b; i--)
#define out(n) printf("%d\n", n)
#define mset(a, b) memset(a, b, sizeof(a))
#define lint long long

using namespace std;

const int INF = 1 << 30;
const int MaxN = 100005;
const double eps = 1e-9;

int sgn(double d)
{
    if(d > eps) return 1;
    if(d < -eps) return -1;
    return 0;
}

struct Point
{
    int x, y;
    Point() {}
    Point(int _x, int _y) : x(_x), y(_y) {}
    void read()
    {
        scanf("%d%d", &x, &y);
    }
};
Point pnt[15][3];
int n;
int a, b;
bool con[15][15];
bool vis[15];

Point operator - (const Point &p1, const Point &p2)
{
    return Point(p1.x - p2.x, p1.y - p2.y);
}

double operator * (const Point &p1, const Point &p2)
{
    return (double)(p1.x * p2.y - p1.y * p2.x);
}

bool get_line_intersection(const Point &p1, const Point &p2, const Point &p3, const Point &p4)
{
    double d1 = (p2 - p1) * (p3 - p1);
    double d2 = (p2 - p1) * (p4 - p1);
    if(0 == sgn(d1 - d2)) return false;
    return true;
}

bool get_segment_intersection(const Point &p1, const Point &p2, const Point &p3, const Point &p4)
{
    if(!get_line_intersection(p1, p2, p3, p4)) {
        if(min(p1.x, p2.x) > max(p3.x, p4.x) || min(p3.x, p4.x) > max(p1.x, p2.x)) return false;
        if(min(p1.y, p2.y) > max(p3.y, p4.y) || min(p3.y, p4.y) > max(p1.y, p2.y)) return false;
        return true;
    }
    double d1 = (p2 - p1) * (p3 - p1);
    double d2 = (p2 - p1) * (p4 - p1);
    double d3 = (p4 - p3) * (p1 - p3);
    double d4 = (p4 - p3) * (p2 - p3);
    int s1 = sgn(d1), s2 = sgn(d2), s3 = sgn(d3), s4 = sgn(d4);
    if(s1 * s2 > 0 || s3 * s4 > 0 || sgn(d1 - d2) == 0) return false;
    return true;
}


bool gao(int x, int y)
{
    if(con[x][y]) return true;
    vis[x] = true;
    repf(i, 1, n) {
        if(!vis[i] && con[x][i]) {
            vis[i] = true;
            bool f = gao(i, y);
            if(f) return true;
        }
    }
    return false;
}

int main()
{
    while(1 == scanf("%d", &n) && n > 0) {
        repf(i, 1, n) {
            pnt[i][0].read();
            pnt[i][1].read();
        }
        mset(con, false);
        repf(i, 1, n) repf(j, 1, n) {
            if(i == j) con[i][j] = true;
            else con[i][j] = get_segment_intersection(pnt[i][0], pnt[i][1], pnt[j][0], pnt[j][1]);
        }
        while(2 == scanf("%d%d", &a, &b)) {
            if(a == 0 && b == 0) break;
            mset(vis, false);
            if(gao(a, b)) puts("CONNECTED");
            else puts("NOT CONNECTED");
        }
    }
    return 0;
}