[F] Longitud de corte

Enlace a Codeforces

Te dan un n-góno(un polígono de n lados) simple (sin intersecciones entre sus lados adyacentes) no necesariamente convexo. También te dan $m$ rectas. Para cada recta debes encontrar la longitud entre los puntos más lejanos que tienen en común la recta y el n-góno.

Los bordes del n-góno pertenecen al polígono. Y se puede dar que el n-góno contenga ángulos de 180 grados.

Entrada

La primera línea contiene dos enteros $n$ y $m$ ($3 \leq n \leq 1000$; $1 \leq m \leq 100$). Las siguientes $n$ líneas contienen las coordenadas de los vértices del polígono (en dirección de reloj o contrarreloj). Todos los vértices son distintos.

Las siguiente $m$ líneas contienen descripciones de las rectas. Cada una contiene las coordenadas de dos puntos distintos de la recta.

Todas las coordenadas dadas son números reales, con a lo más dos dígitos decimales. Además, sus valores absolutos no exceden a $10^5$.

Salida

Imprime $m$ líneas, cada i-ésima línea debería tener la longitud entre los puntos más lejanos que tienen en común el n-góno y la i-ésima recta. La respuesta se considera correcta si el margen de error absoluto o relativo no excede a $10^{-6}$.

Ejemplos

input:
4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1

output:
1.41421356237309514547
1.00000000000000000000
0.00000000000000000000