Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Узким проливом мы плыли, и в сердце теснились стенанья;\
Сцилла с этого боку была, с другого Харибда,\
Страх наводя, поглощала соленую воду морскую.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Одиссея, песнь 12
Корабль Одиссея плывет по длинному проливу постоянной ширины `W` между Сциллой и Харибдой. Сцилла -- многоглавое чудовище,
живущее на западной стороне пролива -- имеет форму многоугольника. А Харибда -- опасный морской водоворот на восточной стороне пролива -- имеет
форму полукруга. Корабль Одиссея настолько мал по сравнению с ними, что можно считать его точкой. Если корабль
пройдет на расстоянии `D` или меньше от Сциллы, то она нападет и сожрет шестерых моряков из команды.
Если же корабль окажется на расстоянии `D` или меньше от Харибды, то его затянет в водоворот и все путники (их на корабле 50) погибнут.
Помогите Одиссею определить минимальное количество людей, которое погибнет при прохождении пролива.
В первой строке ввода содержатся 4 целых числа: ширина пролива `W` (`2<=W<=10^4`), размер опасной
зоны вокруг чудовищ `D`(`1<=D<=10^4`), количество углов в описании Сциллы `N` (`3<=N<=10^5`) и радиус Харибды `R` (`0<R<W`).
С запада пролив ограничен вертикальной линией `x=0`, с востока - линией `x=W`. Центр Харибды находится в точке (`W,0`).
Далее находятся `N` строк по два целых числа в каждой - координаты углов Сциллы ('0<=x<=W', '-10^4<=y<=10^4'). Гарантируется, что
первая и последняя точки имеют x-координаты, равные 0. Точки образуют многоугольник, не обязательно выпуклый. Чудовища
не выходят за пределы пролива, не пересекаются и не касаются.
Если от южного до северного края пролива существует путь, все точки которого находятся на расстоянии строго больше `D` от обоих чудовищ, выведите 0.
Иначе, если существует путь, все точки которого находятся на расстоянии строго больше `D` от Харибды, выведите 6.
Иначе, если любой путь обязательно содержит хотя бы одну точку на расстоянии `D` или меньше от Харибды, выведите 50.
Путь может иметь произвольную форму (не обязательно прямую), но не должен выходить за пределы пролива. Путь
не может проходить внутри чудовищ либо касаться их.
```sample Пример ввода 1
10 1 8 3
0 1
3 4
5 3
3 2
5 2
1 1
6 -4
0 -1
```
```sample Пример вывода 1
0
```
```sample Пример ввода 2
2 1 3 1
0 10
1 11
0 12
```
```sample Пример вывода 2
50
```
Пример безопасного пути для случая 1 изображен на рисунке
Во втором случае любой путь, не выходящий за пределы пролива, пролегает на расстоянии 1 или меньше от Харибды.
Начало
Рабочее место участника
Вычислительная геометрия