·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接http://poj.org/problem?id=1127
题目涉及两个问题：1、判断两个线段是否直接相交（跨立的规范相交或一直线端点在另一直线上的非规范相交） 2、判断两个线段是否能够间接相交
解决第一个问题可以n^2的两两比较一遍，套用计算几何的相交模板即可，第二个问题可以用Floyd传递闭包来解决。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
const double eps = 1e-8;
const double inf = 1e20;
int sgn(double x) {
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
else return 1;
}
struct Point {
double x, y;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() {
scanf("%lf%lf", &x, &y);
}
Point operator - (const Point &b) const {
return Point(x - b.x, y - b.y);
}
double operator ^ (const Point &b) const {
return x * b.y - y * b.x;
}
double operator * (const Point &b) const {
return x*b.x + y*b.y;
}
};
struct Line {
Point s, e;
Line() {}
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
void input() {
s.input();
e.input();
}
int segcrossseg(Line v) {
int d1 = sgn((e-s) ^ (v.s-s));
int d2 = sgn((e-s) ^ (v.e-s));
int d3 = sgn((v.e-v.s) ^ (s-v.s));
int d4 = sgn((v.e-v.s) ^ (e-v.s));
if ((d1^d2) == -2 && (d3^d4) == -2) return 2;
return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
(d4==0 && sgn((e-v.s)*(e-v.e))<=0);
}
};
const int map_size = 14;
int m[map_size][map_size];
Line lines[map_size];
int n;
void floyd() {
int i, j, k;
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if (m[i][j] > m[i][k] + m[k][j])
m[i][j] = m[i][k] + m[k][j];
}
int main() {
int a, b;
while(scanf("%d", &n) != EOF && n) {
for (int i = 0; i < map_size; i++)
for (int j = 0; j < map_size; j++)
m[i][j] = 1;
for (int i = 1; i <= n; i++) {
lines[i].input();
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (lines[i].segcrossseg(lines[j]) > 0)
m[i][j] = 0;
floyd();
while(scanf("%d%d", &a, &b)==2 && !(a==0 && b==0)) {
m[a][b] == 0 ? printf("CONNECTED\n") : printf("NOT CONNECTED\n");
}
}
return 0;
}