Hide

Problem Z
Simple Polygon

A polygon $P$ determined by points $p_1, p_2, \ldots , p_ n$ is a closed chain of line segments (called edges) $p_1 p_2, p_2 p_3, \ldots , p_ n p_1$ in the plane. Polygon $P$ is simple, if no two edges have any points in common, with the obvious exception of two consecutive segments having one common point (called vertex). Note however, that if a vertex is part of any other (third) edge, the polygon is no longer simple.

Any polygon that is not simple is called self-intersecting. In two example figures below, the first polygon is simple, the second one is self-intersecting.

\includegraphics[width=0.9\textwidth ]{drawing.pdf}

Your task is to determine whether a given polygon is simple or self-intersecting.

Input

The input contains at most $150$ test cases. Each test case corresponds to one polygon. First line of the test case contains $N$, the number of points ($1 \leq N \leq 40\ 000$). Each of the following $N$ lines contains coordinates of point $P_ i$, that is $X_ i$, $Y_ i$ separated by space, $1 \leq X_ i, Y_ i \leq 30\ 000$.

The last test case is followed by a line containing zero.

Ouput

For each test case output either “YES” (the polygon is simple) or “NO” (the polygon is self-intersecting).

Sample Input 1 Sample Output 1
5
1 6
5 7
9 4
2 3
6 1
7
1 6
5 7
9 4
4 3
7 4
4 6
3 1
7
1 1
1 4
1 3
2 2
3 1
3 2
2 2
0
NO
YES
NO

Please log in to submit a solution to this problem

Log in