ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Личное первенство УрГУ 2003

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Картины

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Художник Иванов (не тот Иванов, который написал «Явление Христа народу», а один из многих его однофамильцев) смог недорого снять отличную студию. Увы, как он вскоре убедился, дешевизна была вызвана объективными причинами. В доме, где он снимал помещение, когда-то давным-давно произошло убийство, и теперь привидение, живущее в доме, каждую ночь возобновляет на стенах всех комнат кровавые пятна. Проклятие не миновало и студии художника Иванова.
Впрочем, как творческий человек, Иванов быстро придумал простое решение проблемы. Он решил нарисовать одну или две картины и повесить их на той (единственной) стене, на которой появляются пятна так, чтобы кровавые следы оказались полностью закрыты картинами. Конечно же, слишком много времени на эту работу он тратить не хочет — именно поэтому он собирается обойтись не более, чем двумя картинами, и, к тому же, заинтересован в том, чтобы общая площадь этих картин была минимальна.
Все кровавые пятна имеют круглую форму. Каждая картина имеет форму прямоугольника, её стороны параллельны осям координат, минимально возможный размер картины по каждому из измерений — 100 миллиметров. Если потребуется нарисовать две картины, то их надо будет развесить так, чтобы они не налегали друг на друга. Каждое пятно должно быть покрыто ровно одной картиной.

Исходные данные

В первой строке дано количество пятен N, 0 < N ≤ 1000. Далее следует N строк, каждая из которых содержит описание очередного пятна. Пятно описывается тройкой целых положительных чисел: радиусом и координатами центра пятна по осям. Все эти числа даны в миллиметрах и не превосходят 10000.

Результат

Выведите единственное целое число — выраженную в квадратных миллиметрах минимальную площадь двух картин (или одной картины), которых Иванову придётся нарисовать, чтобы закрыть все пятна.

Пример

исходные данныерезультат
3
50 50 50
50 250 50
10 150 250
40000
Автор задачи: Александр Петров (текст — Леонид Волков)
Источник задачи: Ural State University Personal Programming Contest, March 1, 2003
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1245. Картины