e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

2015 German Collegiate Programming Contest (GCPC)

Торт

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

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

prb7708.gif

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

Входные данные

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

Далее следуют n строк, каждая из которых задает целочисленные координаты вершины торта xi и yi (0xi, yi108 для всех 1in). Вершины приведены в том порядке, в котором они образуют строго выпуклую форму.

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

Выходные данные

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #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