CircusTents
SRM 559 · 2012-06-05 · by tehqin
SRM 559 · 2012-06-05 · by tehqin · Geometry
Problem Statement
Problem Statement
The circus is in town. Actually, several different circuses are in town at the same time. This can get confusing for anyone who tries to wait in line for one of the circuses.
All circuses are standing on a large meadow on the edge of the town. Each circus is inside a single big tent. The base of each tent has the shape of a circle.
You were hired by the owner of one of the circuses. The owner wants to place a ticket booth somewhere on the edge of his circus tent. The ticket booth is small, so for the purpose of this problem we will consider it to be a point on the circle that represents the base of the tent.
Often, there is a long queue for the ticket booth. The placement of the queue is completely unpredictable. Sometimes a bad situation may occur: the queue may reach the tent of some other circus. This confuses the people, so the circus owner wants to prevent such bad situations.
Given a location of the ticket booth, its remoteness is the shortest walking distance from the ticket booth to some point on the boundary of a different circus tent. (That is, the length of the shortest curve that does not pass through any of the circles and connects the ticket booth point to a point on one of the other circles.)
You are given threeint[] s: x, y, and r. For each i, there is a circus tent with center at coordinates (x[i], y[i]) and radius r[i]. All the tents are pairwise disjoint. Element 0 of x, y, and r corresponds to the tent that needs the ticket booth. Find the placement of the ticket booth that maximizes its remoteness and return the maximal possible remoteness.
All circuses are standing on a large meadow on the edge of the town. Each circus is inside a single big tent. The base of each tent has the shape of a circle.
You were hired by the owner of one of the circuses. The owner wants to place a ticket booth somewhere on the edge of his circus tent. The ticket booth is small, so for the purpose of this problem we will consider it to be a point on the circle that represents the base of the tent.
Often, there is a long queue for the ticket booth. The placement of the queue is completely unpredictable. Sometimes a bad situation may occur: the queue may reach the tent of some other circus. This confuses the people, so the circus owner wants to prevent such bad situations.
Given a location of the ticket booth, its remoteness is the shortest walking distance from the ticket booth to some point on the boundary of a different circus tent. (That is, the length of the shortest curve that does not pass through any of the circles and connects the ticket booth point to a point on one of the other circles.)
You are given three
Notes
- Your return value must have a relative or an absolute error of less than 1e-9.
Constraints
- x will contain between 2 and 50 elements, inclusive.
- y will contain the same number of elements as x.
- r will contain the same number of elements as x.
- Each element in x will be between -5000 and 5000, inclusive.
- Each element in y will be between -5000 and 5000, inclusive.
- Each element in r will be between 1 and 5000, inclusive.
- No two circus tents will overlap.
- No two circus tents will touch.
Examples
0)
{0,3}
{0,0}
{1,1}
Returns: 3.7390603609952078
There is only one optimal placement of the ticket booth: (-1,0).
1)
{0,3,-3,3,-3}
{0,3,3,-3,-3}
{1,1,1,1,1}
Returns: 2.6055512754639887
There are four optimal ticket booth locations: (-1,0), (1,0), (0,1), and (0,-1).
2)
{3,7,7,7,3}
{4,6,1,-3,0}
{2,2,2,1,1}
Returns: 4.3264459099620725
3)
{10,-1}
{0,0}
{8,2}
Returns: 24.63092458664212
4)
{0,4,-4}
{0,4,-4}
{1,1,1}
Returns: 4.745474963675133
Submissions are judged against all 394 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CircusTents with a public method double findMaximumDistance(vector<int> x, vector<int> y, vector<int> r) · 394 test cases · 2 s / 256 MB per case