시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 35 | 10 | 10 | 71.429% |
A polygon P determined by points p1, p2, . . . , pn is a closed chain of line segments (called edges) p1p2, p2p3, . . . , pnp1 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.
Your task is to determine whether a given polygon is simple or self-intersecting.
The input contains several test cases. Each test case corresponds to one polygon. First line of the test case contains N, the number of points (1 ≤ N ≤ 40 000). Each of the following N lines contains coordinates of point Pi, that is Xi, Yi separated by space, 1 ≤ Xi,Yi ≤ 30 000.
The last test case is followed by a line containing zero.
For each test case output either “YES” (the polygon is simple) or “NO” (the polygon is self-intersecting).
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 3 2 2 0
NO YES NO