`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Задача RECT4

Прямоугольники

На плоскости задан многоугольник. Необходимо написать программу определяющую прямоугольник минимальной площади, который содержит в себе заданный многоугольник, который имеет N вершин.

Ограничения: Все координаты даются в виде действительных чисел в формате,который обрабатывается стандартными функциями ввода-вывода. Оптимальную площадь и координаты прямоугольника необходимо вычислить с точностью до 10-5. 3<=N<=3000,

Ввод-вывод: С клавиатуры вводится количество вершин N, а потом , в следующих N строках -по два действительных числа X Y (через пробел) - координаты вершин многоугольника в порядке их обхода по часовой стрелке. Программа должна вывести на экран 5 строк: в первой строке число S - площадь прямоугольника, а в следующих 4-х строках - пары координат X Yi вершин прямоугольника в порядке их обхода (в произвольном направлении)

Пример:

Ввод>6

Ввод>0.0 0.0

Ввод>3.0 2.0

Ввод>4.0 4.0

Ввод>5.0 2.0

Ввод>8.0 0.0

Ввод>4.0 1.0

Вывод>32.0

Вывод>4.0 4.0

Вывод>0.0 8.0

Вывод>4.0 -4.0

Вывод>0.0 0.0

 

© LIKT 1998-2024