Hide

Problem K
Kingdom of Kittens

In a country far far away, there are so many cats. The cats quickly dominate the whole area, they can even overwhelm humans! Mature cats plan to establish their own kingdom for their own kittens! The first thing to do is setting the border of their kingdom.

One day, they looked around and found $n$ beautiful bushes. They decided to use these bushes to mark the border of their kingdom.

Unfortunately, cats are not so good at geometry, they do not know any shapes except triangles. Hence, they would like to know if they can make a triangle border containing all of these bushes. The triangle border must have positive area. Please help them!

More formally, given $n$ points on a Cartesian coordinate plane, you should determine if there exists a triangle where all these points are on its sides. Points are allowed to coincide with any of the triangle’s vertices. Although all $n$ points have integer coordinates, the triangle’s vertices do not need to have integer coordinates.

Input

The input contains multiple test cases. Each test case is described as below:

  • The first line contains an integer $n$ — the number of points. $(1 \le n \le 10^5)$.

  • In the next $n$ lines, the $i$-th line contains two integers $x_ i$ and $y_ i$ — the coordinates of the $i$-th point. $(-10^9 \le x_ i, y_ i \le 10^9)$.

The input is terminated with a line containing a single $0$.

Sum of $N$ over all test cases in one input file is at most $5 \cdot 10^5$.

Output

For each test case, print ‘YES’ if there is a triangle satisfying the above constraints. Otherwise, print ‘NO’.

Explanation for the first example

\includegraphics[width=0.6\textwidth ]{sample.png}
Sample Input 1 Sample Output 1
4
0 0
0 2
2 0
2 2
5
0 0
0 2
2 0
2 2
1 1
0
YES
NO

Please log in to submit a solution to this problem

Log in