Problem C
Punkt i polygon

Du får givet et simpelt polygon og et søgepunkt, og du skal afgøre, om søgepunktet ligger inden for eller uden for polygonet.

I det 1., 3. og 4. eksempel nedenfor ligger søgepunktet $q$ indenfor; i de øvrige ligger det udenfor.

Input

Indlæsningen består af:

• Én linje med søgepunktets koordinater $q_x$ og $q_y$.

• Én linje med tallet $n$, antallet af polygonets hjørner, hvor $3\leq n\leq 100\, 000$.

• $n$ linjer, hvor for $1\leq i \leq n$ den $i$’te linje indeholder koordinaterne $x_i$ og $y_i$.

Hver koordinat er givet som et reelt tal med decimalpunktum. $x$‑koordinaterne opfylder $0\leq q_x, x_1,\ldots ,x_n\leq 180$. $y$‑koordinaterne opfylder $0\leq q_y, y_1,\ldots ,y_n\leq 90$.

Det er garanteret, at alle punkter er forskellige, og at $(x_1,y_1),\ldots ,(x_n,y_n),(x_1,y_1)$ (i denne rækkefølge) danner randen af et simpelt polygon. Afstanden mellem søgepunktet $q$ og polygonets rand er mindst $10^{-6}$. Det betyder, at punktet garanteret ligger enten strengt inden for eller strengt uden for polygonet.

Output

Skriv “inside” hvis $q$ ligger inden for polygonet. Ellers skriv “outside”.

1.0 1.0
4
0.0 0.0
2.0 0.0
2.0 2.0
0.0 2.0

inside

0.0 0.0
4
1.0 0.0
2.0 1.0
1.0 2.0
0.0 1.0

outside

1.0 1.0
6
0.0 0.0
2.0 0.0
2.0 1.0
3.0 1.0
3.0 2.0
0.0 2.0

inside

1.0 1.0
4
1.0 0.0
2.0 1.0
1.0 2.0
0.0 1.0

inside

1.0 1.0
8
1.0 0.0
2.0 1.0
1.0 2.0
0.0 1.0
0.25 0.75
1.0 1.5
1.5 1.0
0.75 0.25

outside