Задача: Фен шуй

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

К сожалению, ими нельзя покрыть пол комнаты полностью, так как она имеет форму выпуклого многоугольника. Фил хочет минимизировать непокрытую часть пола, располагая ковры оптимальным образом.

Помогите ему расположить два ковра в комнате так, чтобы общая покрытая площадь была максимальна. Ковры можно накладывать друг на друга, но их нельзя загибать и резать.



Входные данные
Первая строка входных данных содержит два целых числа n и r — число углов в комнате (3 ≤ n ≤ 100) и радиус ковров (1 ≤ r ≤ 1000, оба ковра имею один и тот же радиус). Следующие n строк содержат по два числа x_i и y_i — координаты i-го угла  $(–1000 \le x_i; y_i \le 1000)$ . Углы описаны в порядке обхода комнаты по часовой стрелке. Координаты углов различны и соседние стены не коллинеарны.

Выходные данные
Выведите   $x_1, y_1, x_2, y_2$, где($x_1, y_1$) и ($x_2, y_2$) обозначаю центры ковров. Координаты должны иметь точность не менее 4 цифр после точки. Выведите любое оптимальное расположение. Входные данные гарантируют, что решение существует (Фил не стал бы покупать ковер, который не помещается в комнату).

​

Ваш ответ: