Growing Some Oobleck

Oobleck is a fascinating magical substance — leave it in sunlight and it grows in an ever-expanding circle. If two circles ever manage to touch each other, both circles magically merge into one combined circle with area equal to the total of the combined areas of both circles and center at the midpoint of the centers of the two intersecting circles. The expansion rate of this new circle is the maximum rate of both colliding circles. An example of this is shown in Figures 1 and 2.

\includegraphics[width=0.75\textwidth ]{oobleck-f1}

Figure 1: Circle A has center $(10,10)$, radius $6$ and area $36\pi $; circle B has center $(24,10)$, radius $8$ and area $64\pi $.
\includegraphics[width=0.75\textwidth ]{oobleck-f2}
Figure 2: After they merge, they are replaced by circle C with center $(17,10)$, radius $10$ and area $100\pi $.

After a new circle is created it may intersect other existing circles, causing a chain reaction of merges. This combination of an intersection followed by one or more merges is technically known as an ooblection. Ooblections occur instantaneously at the moment of the initial intersection even though they may contain a cascade of merges. If three or more circles are involved in a merge the resulting circle has its center at the average of the centers of all of the circles involved and the resulting area is the sum of all the areas of the circles involved. The expansion rate of the final circle after an ooblection is the maximum rate of any circle involved.

\includegraphics[width=0.8\textwidth ]{oobleck-f3}
Figure 3: A five-circle ooblection.

An example of a five-circle ooblection is shown in Figure 3 (described in Sample Input $2$). At time $t=1$ the circles have expanded to the point shown in Figure 3a. At that time circles A and B merge to form circle F (Figure 3b). Circle F intersects circles C and D, merging to form circle G (Figure 3c). Finally circle G intersects circle E resulting in the final circle H (Figure 3d). All of this takes place at time $t=1$. Circle H has an expansion rate equal to the maximum expansion rate of circles A through E (using the values in Sample Input 2 this maximum growth speed is 2).

Eventually as any set of circles grow, they will eventually ooblect into a single circle. Your task is to find the position and area of that circle the moment it is created.


The input sequence begins with a positive integer $n$ ($n \leq 100$), the number of circles. There then follows $n$ lines, one for each circle. Each line consists of $4$ numbers: $x$ $y$ $r$ and $s$: $x$ and $y$ ($-10^9 \leq x,y \leq 10^9$) specifies the location of the radius of the circle; $r$ ($1 \leq r \leq 10^6$) is the initial radius of the circle; $s$ ($1 \leq s \leq 10^6$) is the expansion rate of the circle. No two circles listed in the input are touching. At most one ooblection begins at any given moment in time, and each ooblection starts with the touching of exactly two circles.


Output two lines. The first line will contain two numbers $x$ $y$, the location of the center of the final circle at the moment it is created. The second line will contain the radius of that circle. Your answers should be accurate to a relative or absolute error of $10^{-6}$.

Sample Input 1 Sample Output 1
1 1 1 1
5 1 1 1
3.00000000 1.00000000
Sample Input 2 Sample Output 2
3 4 5 1
17 4 7 1
10 -13 6 2
10 21 7 1
-7 4 1 1
1.50000000 4.00000000
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.2medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in