UVa 273

From Algorithmist
Jump to: navigation, search

273 - Jack Straws[edit]

Summary[edit]

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

Explanation[edit]

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[edit]

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[edit]

CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED

CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED

CONNECTED

CONNECTED
CONNECTED
CONNECTED

CONNECTED
CONNECTED
NOT CONNECTED