题目大意：给定一些线段，线段之间可能直接连接，也可能间接相连，两种情况都算相连。给定多组询问，判断某两根线段是否相连。
题解
线段的直接相连有两种情况：线段间所在直线有交点，且交点在两条线段上；或者两条线段平行，其中一条线段的端点在另外一条线段上。
线段的间接相连情况可以用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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
using namespace std;
double eps = 1e-8;
const double pi = acos(-1.0);
int cmp(double x){
if(fabs(x) < eps) return 0;
return (x > 0 ? 1: -1);
}
struct Point{
double x, y;
Point(){}
Point(double _x, double _y){
x = _x, y = _y;
}
void input(){
scanf("%lf%lf", &x, &y);
}
void output(){
printf("%.3lf %.3lf\n", x, y);
}
friend bool operator == (const Point &pa, const Point &pb) {
return cmp(pa.x - pb.x) == 0 && cmp(pa.y - pb.y) == 0;
}
friend bool operator < (const Point &pa, const Point &pb) {
return cmp(pa.x - pb.x) == 0 ? cmp(pa.y - pb.y) < 0: pa.x < pb.x;
}
friend Point operator + (const Point &pa, const Point &pb) {
return Point(pa.x + pb.x, pa.y + pb.y);
}
friend Point operator - (const Point &pa, const Point &pb) {
return Point(pa.x - pb.x, pa.y - pb.y);
}
friend Point operator * (const Point &pa, const double &rat) {
return Point(pa.x * rat, pa.y * rat);
}
friend Point operator / (const Point &pa, const double &rat) {
return Point(pa.x / rat, pa.y / rat);
}
//逆时针旋转
friend Point operator << (const Point &pa, const double &rat) {
double sine = sin(rat), cosi = cos(rat);
return Point(pa.x * cosi - pa.y * sine, pa.x * sine + pa.y * cosi);
}
//顺时针旋转
friend Point operator >> (const Point &pa, const double &rat) {
double sine = sin(rat), cosi = cos(rat);
return Point(pa.x * cosi + pa.y * sine, pa.y * cosi - pa.x * sine);
}
double norm() const{
return hypot(x, y);
}
double sqr() const{
return x * x + y * y;
}
};
double dot(const Point &pa, const Point &pb) {
return pa.x * pb.x + pa.y * pb.y;
}
double cross(const Point &pa, const Point &pb) {
return pa.x * pb.y - pa.y * pb.x;
}
double dist(const Point &pa, const Point &pb) {
return hypot(pa.x - pb.x, pa.y - pb.y);
}
//线段之间角
double rad(const Point &pa, const Point &pb){
return acos(dot(pa, pb) / (pa.norm() * pb.norm()));
}
//线段共同点之间角
double rad(const Point &pa, const Point &pb, const Point &pc){
return acos(dot(pa - pc, pb - pc) / ((pa - pc).norm() * (pb - pc).norm()));
}
struct Segment{
Point s, e;
Segment() {}
Segment(const Point &st, const Point &ed){
if(st < ed) s = st, e = ed;
else s = ed, e = st;
}
friend bool operator == (const Segment &sa, const Segment &sb) {
return sa.s == sb.s && sa.e == sb.e;
}
friend double operator * (const Segment &sa, const Segment &sb) {
return dot(sa.e - sa.s, sb.e - sb.s);
}
friend bool operator / (const Segment &sa, const Segment &sb) {
return cross(sa.e - sa.s, sb.e - sb.s);
}
friend Point operator ^ (const Segment &sa, const Segment &sb){
double det1 = cross(sa.s - sb.s, sb.e - sb.s);
double det2 = cross(sa.e - sb.s, sb.e - sb.s);
return (sa.e * det1 - sa.s * det2) / (det1 - det2);
}
bool includes(const Point &pa) const{
return cmp(cross(pa - s, pa - e)) == 0 && cmp(dot(pa - s, pa - e)) <= 0;
}
bool parallel(const Segment &sa) const{
return cmp(cross(sa.e - sa.s, e - s)) == 0;
}
double len() const{
return dist(s, e);
}
};
Segment make_seg(const Point &st, const Point &ed){
return Segment(st, ed);
}
int n;
Segment seg[15];
int con[15][15] = {0};
int main(){
while(scanf("%d", &n) == 1){
if(!n) break;
for(int i = 1; i <= n; ++i){
Point p1, p2;
p1.input(), p2.input();
seg[i] = make_seg(p1, p2);
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i == j){
con[i][j] = 1;
continue;
}
if(seg[i].parallel(seg[j])){
if(seg[j].includes(seg[i].s) || seg[j].includes(seg[i].e))
con[i][j] = 1;
}else{
Point pp = (seg[i] ^ seg[j]);
if(seg[i].includes(pp) && seg[j].includes(pp))
con[i][j] = 1;
}
}
}
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
con[i][j] |= (con[i][k] & con[k][j]);
int u, v;
while(scanf("%d%d", &u, &v) == 2){
if(!u && !v) break;
printf("%s\n", con[u][v] ? "CONNECTED" : "NOT CONNECTED");
}
memset(con, 0, sizeof(con));
}
return 0;
}