Baklažánovi sa nechcelo vymýšľať rozprávku do tejto úlohy a tak si aspoň na papieri vyznačil niekoľko bodov. Po chvíli za ním prišiel Buj, a aby reč nestála sa ho začal pýtať otázky typu: “Koľko tvojich bodov leží v trojuholníku danom týmito tromi bodmi?”. Baklažánovi odpovedanie na tieto otázky dalo vcelku zabrať a teraz ponúka odmenu 20 bodov každému, kto to zvládne tiež.
Úloha
V rovine máme vyznačených \(n\) rôznych bodov s celočíselnými súradnicami. Dostanete \(q\) otázok typu “Koľko vyznačených bodov leží v trojuholníku \(ABC\)?”, kde \(A, B, C\) sú tri rôzne vyznačené body. Vašou úlohou je všetky tieto otázky správne zodpovedať. Strany a vrcholy trojuholníka považujeme za jeho súčasť.
Formát vstupu
V prvom riadku vstupu je jedno celé číslo \(n\) (\(3 \leq n \leq 500\)) – počet bodov. Nasleduje \(n\) riadkov popisujúcich jednotlivé body. V každom z týchto riadkov budú dve celé čísla \(x\) a \(y\) (\(|x|, |y| \leq 1\,000\,000\,000\)) – súradnice daného bodu. Všetky body budú navzájom rôzne. Body si očíslujme v poradí, v akom sú uvedené na vstupe číslami \(0, 1, \dots, n\). V nasledujúcom riadku je jedno celé číslo \(q\) (\(1 \leq q \leq 200\,000\)) – počet otázok. V posledných \(q\) riadkoch sú popisy týchto otázok. Každý z týchto riadkov obsahuje tri celé čísla \(a, b, c\) z rozsahu \(0\) až \(n-1\) – čísla bodov tvoriacich vrcholy trojuholníka, na ktorý sa pýtame. Je zaručené, že body \(a, b\) a \(c\) tvoria (nedegenerovaný) trojuholník.
Formát výstupu
Pre každú otázku vypíšte riadok obsahujúci jedno celé číslo – počet bodov, ktoré ležia v tomto trojuholníku alebo na jeho hranici.
Príklady
Input:
4
0 0
0 3
1 1
3 0
2
0 1 2
3 0 1
Output:
3
4
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.