In machine learning, the problem of linear classification of objects often arises when classes of objects are separated by a linear surface. For example, we have information about the number of days since the registration of an account on a social network and the number of messages sent in the last
day, as well as information about whether this account is a spambot. We can take the age of the account as the X coordinate of the point, and the number of messages & nbsp; for Y
coordinate. The task of classification is to draw a straight line so that objects of one type are on one side of this straight line, and objects of another type on the other side.
With such a straight line, we will be able to predict the type of even an unfamiliar object by the known age of the account and the number of sent messages, depending on which side of the straight line the object turned out to be. Naturally, in real data there may be measurement errors or unusual objects, and it is not always possible to draw such a straight line, because, for example, an object of the first type can accidentally fall into a cluster of objects of the second type and it is impossible to separate it with a straight line.
You need to use the information about the parameters and the type of objects to determine whether there is a straight line that unambiguously separates the classes of objects. The line must not pass through any object.
Input data format
In this problem, the input file contains several test blocks.
The first line contains the number T number of test blocks (1 <= T <= 100).
Each test block consists of N number of described objects (1 <= N <= 2000).
The next N lines contain object descriptions consisting of three integers X, Y , Type (0 <= X, Y <= 107 , 0 < = Type <= 1).
Output format
Print T of the words "YES" or "NO" one per line for each of the test blocks. "YES" should be output if division into classes is possible, "NO" if not possible.
Rating system
Solutions that work correctly for T <= 10, N <= 100 will score at least half of the points.
|
Enter |
Output |
2
6
1 1 1
1 2 1
1 3 0
2 1 1
2 2 0
3 1 0
6
1 3 0
2 2 0
1 2 1
3 1 1
2 1 1
1 1 0
|
YES
NO |