Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1467. Fence relicts
Сканирование, метод двух указателейОлимпиадные задачи на английском языке
| 24/06/2010 | Лето 2010 дорешивание (10F) |
| 14/07/2010 | Лето 2010 - 10 (F) |
Ограничения: время – 4s/8s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
The Nearsea region has a large forest, where many relict trees grow. The local government
decided to create a reservation park with the area between 0 and `S` square meters. The park must
have a shape of rectangle with the sides parallel to coordinate axises.
Environment activists surveyed the forest and found out that it contained `N` relict trees located at
coordinates `(x_i,\ y_i)`, measured in meters.
Find such park location and size that the number of relict trees inside of it or on its boundary is maximum possible.
Input file format
Input file contains integers `N\ S` followed by `N` pairs of integers `x_i\ y_i`.
Output file format
Output file must contain integers `x_a\ y_a\ x_b\ y_b` – coordinates of the two opposite corners of the park.
If there is more than one optimal solution, output any of them.
Constraints
`1\ ≤\ N\ ≤\ 500`, `-10^4\ ≤\ x_i,\ y_i\ ≤\ 10^4`, `1\ ≤\ S\ ≤\ 10^9`
Sample Input 1
5 100 0 0 10 0 10 10 0 10 15 10
Sample Output 1
0 0 10 10
Sample Input 2
3 2 0 0 10 0 20 0
Sample Output 2
0 0 20 0
