DINOSM - Dinosaur Menace
After a failed but interesting DNA project, a lot of dinosaurs spread over the lab devouring
most of the staff. Jeff, a scientist that worked in the project, managed to survive by hiding in
the southwest corner of the lab. Now that all dinosaurs are asleep, he is going to try to leave.
The exit of the lab is located at the northeast corner.
Jeff knows that if any of the dinosaurs wakes up, he does not stand a chance, so he needs to
minimize the likelihood of that happening. For that, he wants to follow a path that maximizes
the minimum distance from him to a dinosaur along the path. The length of the path is of no
interest to Jeff.
For this problem we consider that Jeff and the dinosaurs are points on the plane, and that Jeff’s
path is a continuous curve conecting the southwest and northeast corners of the lab. As we
mentioned, Jeff wants to maximize the minimum distance between this curve and the position
of any dinosaur.
The input contains several test cases, each one described in several lines. The first line of each
test case contains three integers N , W , and H separated by single spaces. The value N is the
number of dinosaurs in the lab (1 ≤ N ≤ 300). The values W (width) and H (height) are the
size of the lab on the x and y coordinates, respectively (2 ≤ W, H ≤ 106 ). This means that
the starting position of Jeff is at (0, 0), while the exit of the lab is located at (W, H). Each
of the next N lines contains two integers X and Y separated by a single space, representing
the coordinates of a different dinosaur (1 ≤ X ≤ W − 1 and 1 ≤ Y ≤ H − 1). Note that no
dinosaur is located on the border of the lab. You may assume that no two dinosaurs have the
same location. The last line of the input contains the number −1 three times separated by
single spaces and should not be processed as a test case.
For each test case output a single line with the maximum possible distance to the closest
dinosaur. Write the result rounded to the closest number with exactly three decimal places,
using the highest in case of ties, as usual.
1 2 2
3 5 4
2 5 4
-1 -1 -1
What is the intended complexity? TLE with O(n*n*log(h+w))...Last edit: 2017-10-16 10:21:56