Задан простой (без самопересечений) n-угольник. Заданный многоугольник не обязательно выпуклый. Также на плоскости задано m прямых. Для каждой прямой выведите длину общей части многоугольника и прямой.
Граница многоугольника является его частью. Многоугольник, возможно, содержит развернутые углы при своих вершинах.
Выходные данные
Выведите m строк. Каждая строка должна содержать длину общей части многоугольника и соответствующей прямой. Допускается абсолютная или относительная погрешность не более 10 - 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1
|
1.41421356237309514547
1.00000000000000000000
0.00000000000000000000
|