e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

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.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
0.875 4
0 0
8 0
8 4
0 4
Çıxış verilənləri #1
4.000000
Giriş verilənləri #2
0.85 5
6 0
12 6
9 12
0 12
3 3
Çıxış verilənləri #2
3.000000
Giriş verilənləri #3
0.999998 4
20008 10000
15004 15005
10001 20009
15005 15004
Çıxış verilənləri #3
1000.000000
Mənbə 2015 German Collegiate Programming Contest (GCPC), June 20, Problem C