Are You Listening?
InterviewTime limit2sMemory limit512 MB
Given your point and n listening circles, find the largest radius centered there overlapping at most two of them; output the floor of it, or 0 if three already cover you.
- Level
Medium4 of 10
- Topics
- Geometry, Math, Sorting, Implementation
- Solved
- No attempts yet
Problem
You are a top government spy currently at a secret location behind enemy lines (ooooh....exciting!). You have a communication device that lets you stay in contact with the various other operatives you work with. The broadcast range of the device is adjustable, and ideally you would set it to its maximum value so you can reach the largest number of operatives. Unfortunately, the enemy is not stupid and has a set of listening devices that can detect your signal. Each listening device has a fixed range (which can vary from device to device), and to pinpoint your location the enemy must detect you on at least three of their listening devices. Therefore, you are safe as long as you set your broadcast range so that at most two listening devices can detect you. A listening device can detect you if your broadcast range and its listening range touch at more than one point.
An example situation is shown below. Your device and its broadcast area are the grey circle, and four listening devices and their detecting areas are the white circles. On the far left you have set your broadcast range so that none of the listening devices can detect you, but clearly you could increase your range. In the middle picture you have increased it so that two of the listening devices can detect you, but that is fine. In the right picture you have increased your range too much, since now three of the listening devices can detect you.
Given your location and the locations and detection ranges of a set of listening devices, determine the maximum broadcast range for your communication device. This range may be 0 if the broadcast device is already within the range of three listening devices.
Input
Input starts with a line containing three integers cx cy n, where (cx, cy) is your location and 3 ≤ n ≤ 100 is the number of listening devices. The next n lines each contain three integers x y r, where (x, y) is the location of a listening device and 0 < r ≤ 1 000 is the radius of its listening area. All coordinates are between −1 000 and 1 000. All n + 1 locations are distinct.
Output
Display the radius of the maximum broadcast area, rounded down to the nearest integer.