Mr . X knows the forest like the back of his hand and never returns empty-
handed when he goes out to pick mushrooms. This year , however , he was in for a
surprise: part of the forest was fenced off and there was some sort of construction
going on behind it...
Mr . X has provided you with a map of the forest with the fence around the
construction site marked. Looking at the map, you can see that the fence is a
polygon that does not intersect with itself. He, however , does not want to disclose
the locations of the mushroom-picking sites... Therefore you have agreed that he
will go to the forest and from time to time call you using his cell phone to ask if he
can visit one or another place in the forest.
Write a program to answer his queries.
The first line of each testcase
contains N (3 ≤ N ≤ 100,000), the number of vertices of the polygon, and M
(0 ≤ M ≤ 100,000), the number of queries. Each of the following N lines contains
two integers in the range -100,000...100,000, the coordinates of the vertices of the
polygon in the order in which they appear on the perimeter . It is known that the only common point between any two edges is the common endpoint they share if
they are incident. Each of the following M lines also contains two integers in the
range -100,000...100,000, the coordinates of the points Mr . X queries you about.
each testcase should consist of exactly M lines, one
for each query. The line should contain the word Inside if the point queried
about is inside the polygon, the word Outside if the point is outside the polygon,
and the word Border if the point lies on an edge of the polygon.
4 4 1 2 3 -2 0 -1 -3 -2 2 0 1 -1 -2 1 1 2
Border Inside Outside Border
Migrated from old NTUJ.
icpc2008, neerc west
| No. | Testdata Range | Score |
|---|