UVa 10803

From Algorithmist
Jump to navigation Jump to search

10803 - Thunder Mountain[edit]

Summary[edit]

Given points in the plane, construct a graph following the rules, and find the longest of the all-pairs shortest path. If it not connected, then print "Send Kurdy".

Explanation[edit]

Use an All-Pairs Shortest Path algorithm, and go through each possible connections, find the max of the shortest paths. If the graph is disconnected, print "Send Kurdy". Remember to use integers when possible.

Input[edit]

2
5
0 0
10 0
10 10
13 10
13 14
2
0 0
10 1

Output[edit]

Case #1:
25.0000

Case #2:
Send Kurdy