Problem K
Knightly Knowledge

Ancient cultures had an enormous and mostly unexpected knowledge of the earth and geometry. When they were building monuments, they did not place them at arbitrary locations. Instead, each building spot was carefully selected and calculated. Nowadays we can observe this in the form of so-called ley lines. A ley line is a horizontal or vertical straight line of infinite length that runs through at least two ancient monuments. Ley lines are expected to be a source of some kind of magic energy and every church built along such a line is a mighty church.

There are already several monuments and churches. An ancient culture is planning to construct a new monument, but the location is yet to be determined. They are looking for the spot that will turn the most ordinary churches into mighty churches. The monument can be co-located with a church or an existing monument – in that case, the new monument will simply be built around the church or monument.

\includegraphics[width=0.6\textwidth ]{sample2}
Figure 1: Illustration of Sample 2 with 2 ley lines ( blue| ), 6 monuments ( \includegraphics[height=\fontcharht \font `\B ]{monument}), 2 mighty churches (\scalebox 1.5 \includegraphics[height=\fontcharht \font `\B ]{mightychurch} ) and 3 ordinary churches (\scalebox 1.5 \includegraphics[height=\fontcharht \font `\B ]{church} ) that are turned into mighty churches when building the dashed monument.


The input consists of:

  • One line with two integers $m$ and $c$ ($0 \le m, c \le 1\, 000$), the number of already built monuments and churches.

  • $m$ lines with the coordinates of the monuments.

  • $c$ lines with the coordinates of the churches.

All coordinates are given as two integers $x$ and $y$ ($-10^6 \le x, y \le 10^6$). None of the given coordinate pairs coincide with one another, but any may coincide with the location of the new monument.


Output three integers: the coordinates for where to build the new monument and the number of ordinary churches that will be turned into mighty churches with this new monument. The coordinates should be in the range ($-10^6 \le x, y \le 10^6$). If there are multiple optimal solutions, you may output any one of them.

Sample Input 1 Sample Output 1
2 3
0 5
5 0
0 1
0 3
3 0
0 0
Sample Input 2 Sample Output 2
6 5
-6 0
-4 0
-3 0
-4 -2
-3 -2
-2 -3
-6 -1
-4 -1
-3 -1
-5 -3
0 -3
-6 -3
Sample Input 3 Sample Output 3
1 2
0 0
1 0
0 1
0 0
CPU Time limit 3 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in