images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
25/04/2024 21:47:18

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

751. Черное пятно

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Жила-была мать с дочкой. Однажды они переехали в новую квартиру. А в одной комнате на стене было чёрное пятно. Мать попыталась это пятно закрасить, но на следующий день пятно появилось снова, а рядом с ним еще одно. Тогда мать попыталась заклеить пятна обоями, но на следующий день пятен стало больше прежнего…
Тогда они решили завесить пятна ковром…
На стене несколько пятен круглой формы. Нужно закрыть как можно больше пятен прямоугольным ковром. При этом стороны ковра должны быть параллельны осям координат.
Напишите программу, определяющую расположение ковра, при котором он закрывает наибольшее число пятен. Пятно считается закрытым, если оно закрыто ковром полностью.
В первой строке ввода содержатся три целых числа, разделенных пробелами – количество пятен `N` (`1\ ≤\ N\ ≤\ 1000`) и длины сторон ковра `A` и `B` (`1\ ≤\ A,\ B\ ≤\ 1000`). Далее следует `N` строк, в каждой строке содержатся три целых числа – координаты центра `i`-го пятна `X_i`, `Y_i` (`0\ ≤\ X_i,\ Y_i\ ≤\ 1000`) и его радиус `R_i` (`1\ ≤\ R_i\ ≤\ 100`). Пятна не пересекаются между собой.
Вывести в первой строке четыре целых числа – координаты противоположных углов ковра, при котором он закрывает наибольшее число пятен. Если существует несколько вариантов – вывести любой.

Пример ввода

3 100 50
0 50 5
50 70 1
20 90 5

Вывод для примера

-5 45 95 95
loading