# UVa 273

Jump to navigation
Jump to search

## 273 - Jack Straws[edit]

## Summary[edit]

This problem is a Connected Components problem. Two straws are connected if they intersect, and since , 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