SRM 559 1 900 CircusTents

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 three int[]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.

Definition

Limits

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.

Test cases

0. input

   • x { 0, 3 }
   • y { 0, 0 }
   • r { 1, 1 }

   output

   Returns 3.7390603609952078

   note

   There is only one optimal placement of the ticket booth: (-1,0).
1. input

   • x { 0, 3, -3, 3, -3 }
   • y { 0, 3, 3, -3, -3 }
   • r { 1, 1, 1, 1, 1 }

   output

   Returns 2.6055512754639887

   note

   There are four optimal ticket booth locations: (-1,0), (1,0), (0,1), and (0,-1).
2. input

   • x { 3, 7, 7, 7, 3 }
   • y { 4, 6, 1, -3, 0 }
   • r { 2, 2, 2, 1, 1 }

   output

   Returns 4.3264459099620725
3. input

   • x { 10, -1 }
   • y { 0, 0 }
   • r { 8, 2 }

   output

   Returns 24.63092458664212
4. input

   • x { 0, 4, -4 }
   • y { 0, 4, -4 }
   • r { 1, 1, 1 }

   output

   Returns 4.745474963675133