eolymp
bolt
Try our new interface for solving problems
Problems

Zombie Containment

Zombie Containment

\includegraphics{https://static.e-olymp.com/content/d6/d64b5f00cc3b67ba2a12ec568dbfbdf21c849cd3.jpg} Associated with the zombie apocalypse is the notion of a critical mass of zombies: once the number of zombies exceeds a certain threshold \textbf{T}, all is lost. Your city is in a precarious state: its current population is \textbf{3T}. Even worse, you suspect someone in the city may be infected, although you have no idea who it may be. Once the symptoms manifest, it will be too late for that person, as well as for everyone else in the city that person can reach. To prevent the possibility of reaching critical mass, you are going to divide the city into \textbf{3} regions via a set of walls. The city is triangular, and so you are going to divide the city into \textbf{3} smaller triangles by choosing a single splitting point and erecting straight walls between that point and the three vertices of the outer wall. This must be done immediately, i.e., there is no time to relocate people. Can you find a splitting point such that the three resulting regions each have exactly \textbf{T} people? \InputFile Consists of multiple test cases. Each test case is formatted as follows: \begin{itemize} \item Line \textbf{1}: An integer \textbf{n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{30000}) denots the number of people, \textbf{n }is always a multiple of \textbf{3}. \item Lines \textbf{2 }to \textbf{4}: Two numbers \textbf{x_i} and \textbf{y_i} (\textbf{-10 }≤ \textbf{x_i}, \textbf{y_i} ≤\textbf{ 10}) denoting the coordinates of the \textbf{i}^th corner of the city. The three corners are specified in counterclockwise order. \item Lines \textbf{5 }to \textbf{n + 4}: Two numbers \textbf{x_i} and \textbf{y_i} (\textbf{-10 }≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10}) denoting the coordinates of the \textbf{i^th} person. All people lie in the interior of the city triangle. \end{itemize} Input is followed by a single line with a \textbf{0}, which should not be processed. It is guaranteed that no two people will be collinear with any of the corners of the city. In particular, it is guaranteed that for any two people \textbf{I }and \textbf{J }and any corner \textbf{A }the angle \textbf{IAJ }will be at least \textbf{10^\{-7\}} rad. \OutputFile For each test case, print out a single line with two numbers \textbf{x }and \textbf{y }denoting the splitting point of the city. Each person must lie in the interior of one of the three generated triangles. Assume a person is a single point with zero radius, and that a wall is a line with zero thickness. It is guaranteed that there exists a splitting point; in fact, it is guaranteed that there exists a splitting point such that if the point were moved by \textbf{10^\{-7\}} in any direction, it would still be a splitting point. Any splitting point that partitions the people into \textbf{3 }sets of equal size will be judged correct.
Time limit 1 second
Memory limit 64 MiB
Input example #1
3
0.0 0.0
10.0 0.0
0.0 10.0
4.0 4.0
1.0 4.0
4.0 1.0
0
Output example #1
3.0 3.0
Source 2010 ACM North America - Pacific Northwest, Problem B