# UVa 273

Jump to navigation Jump to search

## Summary

This problem is a Connected Components problem. Two straws are connected if they intersect, and since ${\displaystyle N\leq 13}$, Floyd-Warshall's Algorithm should suffice.

## Explanation

Two straws are connected either if they intersect (a segment-segment intersection), or they connect through other straws. Preprocessing the given implicit graph using Floyd-Warshall's Algorithm into a reachability graph, and the queries are trivial.

## Input

5

7
1 6 3 3
4 6 4 9
4 5 6 7
1 4 3 5
3 5 5 5
5 2 6 3
5 4 7 2
1 4
1 6
3 3
6 7
2 3
1 3
0 0

7
1 6 3 3
4 6 4 9
4 5 6 7
1 4 3 5
3 5 5 5
5 2 6 3
5 4 7 2
1 4
1 6
3 3
6 7
2 3
1 3
0 0

2
2 76 99 85
61 85 86 48
2 1
0 0

2
0 2 0 0
0 0 0 1
1 1
2 2
1 2
0 0

2
0 0 1 1
10 1 15 1
1 1
2 2
1 2
0 0


## Output

CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED

CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED

CONNECTED

CONNECTED
CONNECTED
CONNECTED

CONNECTED
CONNECTED
NOT CONNECTED