Олон өнцөгт доторх цэг

2s

512MB

1560

0%

Geometry

$n$ орой бүхий олон өнцөгт ба $m$ цэгийн жагсаалт өгөгдөнө. Цэг бүр олон өнцөгтийн дотор, гадна эсвэл зааг дээр байгааг тогтоо.

Олон өнцөгт $n$ орой $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ -ээс тогтоно. $i=1,2,\dots,n-1$ үед $(x_i,y_i)$ ба $(x_{i+1},y_{i+1})$ оройнууд хөрш, мөн $(x_1,y_1)$ ба $(x_n,y_n)$ оройнууд хөрш.

https://cses.fi/problemset/task/2192

Оролтын формат

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо байна: олон өнцөгтийн оройнуудын тоо ба цэгүүдийн тоо.

Дараагийн $n$ мөрөнд олон өнцөгтийг тодорхойлно. $i$ дэх мөрөнд $x_i$ , $y_i$ хоёр бүхэл тоо байна.

Олон өнцөгт энгийн, өөрөөр хэлбэл өөрөө өөрийгөө огтлолцдоггүй гэж үзнэ.

Дараагийн $m$ мөрөнд цэгүүдийг тодорхойлно. Мөр бүрт $x$ , $y$ хоёр бүхэл тоо байна.

Гаралтын формат

Цэг бүрд "INSIDE", "OUTSIDE" эсвэл "BOUNDARY" гэж хэвлэ.

Хязгаарлалт

$3 \le n,m \le 1000$
$1 \le m \le 1000$
$-10^9 \le x_i, y_i \le 10^9$
$-10^9 \le x, y \le 10^9$

Жишээ

Оролт1

Гаралт1

INSIDE
OUTSIDE
BOUNDARY

0.1 / 64 KiB

Редактор уншиж байна...