#C7815. Point Classification in a Convex Polygon
Point Classification in a Convex Polygon
Point Classification in a Convex Polygon
You are given a convex polygon defined by n vertices listed in counterclockwise order, and a set of query points. Your task is to determine for each query point whether it lies inside the polygon, on the boundary (including vertices and edges), or outside the polygon.
The polygon is convex, and the points are given as integer coordinates. Note that if a point lies exactly on an edge or vertex, it is considered to be on the boundary. Use appropriate geometric techniques (e.g. ray casting or angle summation) with careful handling of boundary cases to determine the location of the point.
Input and Output Format:
- The input is read from standard input.
- The output should be printed to standard output, with each result on a new line.
Example:
Input: 4 0 0 4 0 4 4 0 4 3 2 2 4 4 6 6</p>Output: inside boundary outside
inputFormat
The first line of input contains an integer n (3 ≤ n ≤ 100), the number of vertices of the convex polygon.
The next n lines each contain two integers, representing the coordinates of the polygon's vertices in counterclockwise order.
The next line contains an integer q, the number of query points.
The following q lines each contain two integers, representing the coordinates of a query point.
All input is read from standard input.
outputFormat
For each query point, output one line containing one of the words: inside
, boundary
, or outside
indicating whether the point lies inside, on the boundary, or outside the convex polygon respectively. The output is printed to standard output.
4
0 0
4 0
4 4
0 4
3
2 2
4 4
6 6
inside
boundary
outside
</p>