POJ 1127 Jack Straws （线段相交+并查集）
2014-09-16 11:01:47         来源：GLSilence的专栏

Jack Straws

```#include
#include
#include
#include
#define sqr(x) ((x)*(x))
#define zero(x) (((x) > 0 ? (x) : (-x)) < eps)
using namespace std;
const double eps = 1e-8;

struct Point {
double x, y;
} ;
struct Line {
Point a, b;
} L[20];

double xmult(Point a, Point b, Point c) {
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

///若共线，返回1;不共线，返回0。
int dot_inLine(Point p1, Point p2, Point p3){
return zero(xmult(p1, p2, p3));
}

///判两点在线段同侧,点在线段上返回0
int same_side(Point p1, Point p2, Line l){
return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
}

///判点是否在线段上,包括端点
int dot_onLine_in(Point p, Line l){
return zero(xmult(p, l.a, l.b)) && (l.a.x-p.x)*(l.b.x-p.x) < eps && (l.a.y-p.y)*(l.b.y-p.y) < eps;
}

///判两线段相交,包括端点和部分重合
int intersect_in(Line u, Line v){
if (!dot_inLine(u.a, u.b, v.a)
|| !dot_inLine(u.a, u.b, v.b))
return !same_side(u.a, u.b,v) && !same_side(v.a, v.b,u);
return dot_onLine_in(u.a, v) || dot_onLine_in(u.b, v)
|| dot_onLine_in(v.a, u) || dot_onLine_in(v.b, u);
}

int f[100];

int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}

void unionSet(int x, int y) {
x = find(x);
y = find(y);
if(x != y) {
f[x] = y;
}
}

int main()
{
int n;
while(~scanf(%d, &n) && n) {
for(int i = 1; i <= n; ++i) {
f[i] = i;
}
for(int i = 1; i <= n; ++i) {
scanf(%lf%lf%lf%lf, &L[i].a.x, &L[i].a.y, &L[i].b.x, &L[i].b.y);
}
int p, q;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(intersect_in(L[i], L[j])) {
unionSet(i, j);
}
}
}
while(scanf(%d%d, &p, &q) && (p||q)){
if(find(q) == find(p)) {
puts(CONNECTED);
}
else {
puts(NOT CONNECTED);
}
}
}

return 0;
}
```