Самое экстравагантное дупло

В Звенящем Лесу проводится конкурс на самое экстравагантное дупло. Правда, в целях экономии нервов зрителей, конкурс проводится среди макетов, а не самих дупел.

В качестве исходного материала каждому из участников предоставляется доска размером 20 000 x 20 000 метров. Макет элементарного дупла представляет собой окружность, аккуратно выдолбленную на плоскости. Макет же экстравагантного дупла представляет из себя несколько макетов элементарных дупел, выдолбленных на одной доске.

Каждому участнику уже заданы радиусы всех элементарных дупел, которые он должен выдолбить. Более того, даже последовательность их выдалбливания строго зафиксирована. Таким образом, единственное, что каждый из участников может варьировать – это координаты центра каждого элементарного дупла.

Казалось бы, все возможности для свободного творчества уже перекрыты, но это не так. Во-первых, каждому элементарному дуплу соответствует некоторое изначальное количество баллов. Во-вторых, сразу после выдалбливания очередного элементарного дупла за него начисляется итоговый балл, равный сумме изначального балла за это дупло и всех итоговых баллов за уже выдолбленные элементарные дупла, с которыми данное дупло пересекается. Итоговый балл за экстравагантное дупло начисляется как сумма итоговых баллов за все элементарные дупла, из которых оно состоит. Два дупла считаются пересекающимися, если соответствующие им на макете окружности пересекаются, либо одна лежит внутри другой. Касания окружностей на макете недостаточно, чтобы считать дупла пересекающимися.

Вам предлагается примерить на себя шкуру дятла и написать программу, которая по заданным радиусам элементарных дупел, баллов за них, а также последовательности их выдалбливания определила бы координаты центров элементарных дупел, да так, чтобы получившееся экстравагантное дупло имело бы максимальный возможный итоговый балл.

Входные данные

В первой строке входного файла INPUT.TXT задано число n – количество элементарных дупел, которые надо задействовать (1 ≤ n ≤ 1 000). Далее следуют n строк, каждая из которых описывает соответствующее дупло и содержит два целых числа: r_i и c_i (0 < r_i, c_i ≤ 1000), где r_i – радиус соответствующего дупла в метрах, а c_i – изначальное количество баллов, соответствующее данному элементарному дуплу. Дупла даны в порядке выдалбливания.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать ровно n строчек, в каждой по два числа – координаты центра соответствующего элементарного дупла в метрах с точностью не менее 10⁻⁶ метра. Кроме того, макеты дупел не должны выходить за пределы исходной доски, а расстояние между любыми двумя центрами должно быть не менее сантиметра. Точка (0, 0) соответствует центру исходной доски. Если возможны несколько вариантов расстановки дупел, дающих максимальный балл, выведите любой.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]