Proste 2

Limit pamięci: 64 MB

Odległością prostej od wielokąta nazywamy najmniejszą odległość jakiegokolwiek punktu należącego do tego wielokąta od tej prostej (przez wielokąt rozumiemy tu zarówno jego brzeg, jak i wnętrze). Od wielokąta nie wymagamy, żeby był wypukły, nie miał wierzchołków wielokrotnych czy samoprzecięć brzegu.

Zadanie

Napisz program który:

• wczyta ze standardowego wejścia opis wielokąta i opisy pewnej liczby prostych,
• dla każdej prostej wyznaczy najmniejszą odległość od wielokąta,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające liczbę boków wielokąta oraz liczbę prostych do przeanalizowania. Kolejnych wierszy zawiera po dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające współrzędne -tego wierzchołka wielokąta. Pary wierzchołków następujące bezpośrednio po sobie, podobnie jak pierwszy i ostatni wierzchołek, wyznaczają krawędzie wielokąta. Następne wierszy zawiera po trzy liczby całkowite , i (, ), pooddzielane pojedynczymi odstępami i definiujące prostą o równaniu .

Wyjście

Wyjście powinno się składać z wierszy. -ty wiersz wyjścia powinien zawierać kwadrat odległości -tej prostej od wielokąta, zapisany w postaci ułamka prostego nieskracalnego, w którym licznik od mianownika jest oddzielony znakiem ukośnika ().

Przykład

Dla danych wejściowych:

8 2
2 1
6 1
6 2
3 2
3 5
5 5
5 7
2 7
1 1 -2
1 0 -6

1/2
0/1

Autor zadania: Jakub Radoszewski.