#C11378. Non-intersecting Cycle Formation
Non-intersecting Cycle Formation
Non-intersecting Cycle Formation
You are given n points in the plane, each with integer coordinates. Your task is to determine whether it is possible to connect these points with line segments to form a single cycle such that:
- Every point is connected to exactly two other points.
- No two line segments intersect except at the endpoints.
A key observation is that such a formation exists if and only if n is even, i.e., $$n \mod 2 = 0$$.
For example, if there are 4 points, it is possible to form a cycle, whereas with 5 points it is impossible.
inputFormat
The input is given via standard input (stdin) and has the following format:
n x1 y1 x2 y2 ... xn yn
Where n
is the number of points, and each of the next n
lines contains two integers representing the coordinates of a point.
outputFormat
Output a single line to standard output (stdout):
POSSIBLE
If a non-intersecting cycle formation is possible, or
IMPOSSIBLE
if it is not possible.
## sample4
0 0
2 2
2 0
0 2
POSSIBLE
</p>