시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Gustav se voli zabavljati s geometrijskim problemima. Proučavao je razne geometrijske probleme na internetu i naišao na jedan koji ne zna riješiti, pa mu stoga pomognite da riješi sljedeći problem. Zadan je konveksni mnogokut i skup pravaca koji sijeku mnogokut.
Za svaki od zadanih pravaca potrebno je odrediti udaljenost od mnogokuta (udaljenost pravca i najbližeg vrha mnogokuta).
Pravac siječe mnogokut ako i samo ako ima barem jednu zajedničku točku s unutrašnjosti mnogokuta. Niti jedan pravac neće biti paralelan s nekom od stranica mnogokuta.
U prvom retku N (1 ≤ N ≤ 100 000), broj vrhova mnogokuta.
U sljedećih N redaka dva prirodna broja po apsolutnoj vrijednosti manja od 109 – koordinate vrhova konveksnog mnogokuta.
Vrhovi su dani u smjeru kazaljke na satu.
U sljedećem retku nalazi se broj M (1 ≤ M ≤ 100 000), broj pravaca.
U sljedećih M redaka tri prirodna broja A, B, C (1 ≤ A, B, C ≤ 109 ) koji predstavljaju pravac Ax + By + C = 0. Svaki od zadanih pravaca siječe mnogokut.
M redaka, u retku i se nalazi jedan realan broj zaokružen na 3 decimale – udaljenost mnogokuta te i-tog pravca.
4 0 2 2 0 0 -2 -2 0 1 0 4 -5
0.750
3 0 6 6 0 0 0 2 2 4 -13 0 1 -2
0.224 2.000