eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Торт

Торт

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

София любит печь пироги и делиться ими с друзьями. На свадьбу ее лучшей подруги Беа она сделала специальный торт, используя только лучшие ингредиенты которые смогла достать, после чего добавил картинку на вершину торта. Для того чтобы сделать торт еще более особенным, она сделала его форму ни круглой ни квадратной, но выпуклой. София решила отправить торт на вечеринку специальным курьером. К сожалению, пирог оказался немного тяжелым, а для упаковки избыточный вес недопустим. Поэтому София решила удалить некоторые части пирога, чтобы сделать его легче.

София хочет разрезать торт следующим образом: сначала она выбирает действительное число s2. Для каждой вершины для каждого смежного ребра торта она отмечает место 1 / s части длины ребра. Затем для каждой вершины она делает разрез между двумя отметками, таким образом удаляя вершину.

prb7708.gif

София не хочет отрезать больше от пирога больше чем это необходимо по очевидным причинам. Можете ли вы помочь ей выбрать s?

Вхідні дані

Первая строка содержит действительное число a и целое число n (0.25a < 1, 3n100), где a указывает на отношение веса, разрешенного перевозчиком, а n - число вершин в торте. a задано с не менее 7 десятичными цифрами.

Далее следуют n строк, каждая из которых задает целочисленные координаты вершины торта x[i] и y[i] (0x[i], y[i]10^8 для всех 1in). Вершины приведены в том порядке, в котором они образуют строго выпуклую форму.

Вы можете смело предположить, что вес равномерно распределен по площади пирога. Кроме того, торт всегда можно разрезать для некоторого такого s (2s1000), что отношение веса остатка торта к весу исходного торта равна a.

Вихідні дані

Вывести наибольшее значение s, такое что отношение остатка торта к исходному весу составит не более a.

Ответ следует выводить с точностью не менее 10^(-4).

Приклад

Вхідні дані #1
0.875 4
0 0
8 0
8 4
0 4
Вихідні дані #1
4.000000
Вхідні дані #2
0.85 5
6 0
12 6
9 12
0 12
3 3
Вихідні дані #2
3.000000
Вхідні дані #3
0.999998 4
20008 10000
15004 15005
10001 20009
15005 15004
Вихідні дані #3
1000.000000
Джерело 2015 German Collegiate Programming Contest (GCPC), June 20, Problem C