Однажды четверо римских торговцев встретились в одном из римских мансионов, чтобы обсудить свои торговые планы. У торговцев была следующая проблема: торговали они одним и тем же видом товара, поэтому, если они занимались торговлей в одном и том же городе, неизбежно терпели убытки. Было решено распределить города, в которых будет вестись торговля, между собой.
Карту Рима можно в этой задаче представить как плоскость, на которой в некоторых местах отмечены точки — города Римской империи.
Торговцы хотят выбрать некоторую разделяющую точку \((x_0, y_0)\). Затем в городе с координатами \((x_i, y_i)\) будет торговать только
- первый торговец, если \(x_0 \le x_i\) и \(y_0 \le y_i\);
- второй торговец, если \(x_0 > x_i\) и \(y_0 \le y_i\);
- третий торговец, если \(x_0 \le x_i\) и \(y_0 > y_i\);
- четвертый торговец, если \(x_0 > x_i\) и \(y_0 > y_i\).
Торговцы хотят выбрать точку \((x_0, y_0)\) так, чтобы максимизировать минимальное количество городов, которое достанется кому-либо из них торговцев (то есть максимально честно). Помогите им найти такую точку.
Выходные данные
В первой строке выведите одно целое число \(k\) (\(0 \le k \le \frac{n}{4}\)) — максимально возможное количество городов, которое достанется каждому торговцу.
Во второй строке выведите два целых числа \(x_0\) и \(y_0\) (\(|x_0|, |y_0| \le 10^9\)) — координаты разделяющей точки. Если подходящих точек может быть несколько, то разрешается вывести любую из них.
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 1
1 2
2 1
2 2
4
0 0
0 0
0 0
0 0
8
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1
|
1
2 2
0
0 0
2
1 0
0
0 0
|