IITWPC4C - Maggu and Vectors

no tags 

Maggu was teaching vectors using triangle diagrams to to his little brother. Now in the midst of lesson he went for a coffee and on returning finds all his triangles disassembled into constituent vectors by his naughty brother. He needs to recreate the triangles. He needs your help in doing this task quickly as he has to go for an internship interview.

Input

First line will contain T (1 <= T <= 10), the number of test cases. Each test case will consist of first line N, number of vectors. Next line will contain N (1 <= N <= 1000) vectors of the form of a b (-1000 <= a, b <= 1000).

Output

You have to print, in a new line for every test case, “YES” if any 3 vectors among N form a triangle, “NO” otherwise.

Example

Input:
3
5
3 4 3 -4 5 0 6 0 3 5
2
4 5 -4 -5
3
1 2 3 4 -5 -6

Output:
YES
NO
NO

hide comments
Simes: 2017-12-09 21:19:16

@nadstratosfer: me neither, but spojtoolkit gives YES for the first case and NO for the second. Doesn't it only show there are no cases like that in the test data? @praveen, could you add these cases and rejudge?

nadstratosfer: 2017-12-09 15:58:43

Good catch with the second case Simes, but the first one seems to prove that it's the judge solution that is bad. I can't see how could a triangle be built of these vectors.

Simes: 2017-12-09 15:18:37

Input looks ok to me, but poor test cases, since my AC code and spojtoolkit give different results for
2
5
1 2 3 4 -5 -6 -6 -5 4 3
3
0 -1 1 0 -1 1

nadstratosfer: 2017-12-09 02:47:18

Malformed input, use C-style ("get next integer") reading in Python to avoid NZEC.

Piyush Kumar: 2015-06-13 11:50:54

By triangles does it mean triangles satisfying any of these two conditions :
a+b+c=0 , a+b=c ? where (a,b,c) are vectors

candide: 2014-05-11 12:55:27

raw brute force is enough to get AC ;)

@nitish rao
vector(3, 4)+ vector(3, -4) = vector(6, 0)
@Shiva Mahajan
the correct output is NO

As noted by JP, only true triangles are allowed, points lying in some line are not valid triangles.

Last edit: 2014-05-15 16:02:53
nitish rao: 2014-03-22 15:45:46

Can anyone explain the o/p for 1st test case?

NISHANT RAJ: 2014-03-16 14:07:55

after many WA ... finally got AC

Shiva Mahajan: 2014-02-05 20:36:12

what should be the output for
3
0 0 0 0 0 0

Last edit: 2014-02-05 22:45:23
Jacob Plachta: 2014-02-03 19:52:33

Some clarifications:
1. Vectors with length 0 (a=b=0) can be given
2. Degenerate triangles don't count


Added by:praveen123
Date:2014-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64