Олимпиадный тренинг

Задача . Лестницу в треугольник


На плоскости дана геометрическая фигура "лестница". Она имеет N ступенек, которые заданы положительными координатами. Каждая ступень имеет свою высоту и ширину. Требуется найти прямую, которая отсекает от некоторых ступеней "лестницы" треугольники так, что из полученных фигур можно сложить прямоугольный треугольник такой же площади, что и исходная фигура. Разрешается, чтобы отсекаемые от ступеней треугольники соприкасались только вершинами (но не сторонами).

Формат входных данных:
В первой строке дано число 0 <= N <= 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < xi, yi < 106 - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

Формат выходных данных:
Ответ содержит одну строку: два числа через пробел - высота и ширина получившегося прямоугольного треугольника. Если существует несколько решений, то вывести любое. Результат выводится с точностью до четырех десятичных знаков после запятой. В случае, когда решение отсутствует, вывести два ноля через пробел

Примечание

Примеры
Входные данныеВыходные данные
1 2
1 3
3 1
0.0000 0.0000
2 2
2 3
3 2
4.0000 4.0000

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Free Pascal1
Комментарий учителя