Фен шуй – это древняя китайская практика размещения предметов в пространстве для достижения гармонии. В ней говорится, что пол не должен быть пустым, поэтому Фил разместил на полу два одинаковых круглых ковра (по фен шуй надо избегать прямых линий и острых углов).
К сожалению, ими нельзя покрыть пол комнаты полностью, так как она имеет форму выпуклого многоугольника. Фил хочет минимизировать непокрытую часть пола, располагая ковры оптимальным образом.
Помогите ему расположить два ковра в комнате так, чтобы общая покрытая площадь была максимальна. Ковры можно накладывать друг на друга, но их нельзя загибать и резать.
.png)
Входные данные
Первая строка входных данных содержит два целых числа 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 цифр после точки. Выведите любое оптимальное расположение. Входные данные гарантируют, что решение существует (Фил не стал бы покупать ковер, который не помещается в комнату).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
-2 0
-5 3
0 8
7 3
5 0
|
-2.1715728753 3.0000000000 4.2617090669 2.4981148759
|
|
2
|
4 3
0 0
0 8
10 8
10 0
|
3.0000000000 5.0000000000 7.0000000000 3.0000000000
|