Make A Square

Problem code: MKSQR

All submissions for this problem are available.

Statement

You are give a set of 2-d vectors (x,y) [ -10^8 ≤ x,y ≤ 10^8, x ≠ y ] of size n (1 ≤ n ≤ 50000 ). Lets denote the ith vector as vi.
You are to determine if the following system of equations has a solution :
a1*v1 + a2*v2 + a3*v3 + ... ai*v1 + ... an*vn = (k,k) for some arbitrary k.
All ai's are non-negative integers [ 0 ≤ ai ≤ 10^16 ] and
ALL ai's CANNOT BE ZERO ;).
In other words, you need to find some linear combination of these vectors with positive coefficient such that you end up with a vector(a,b) with a=b.

Input

First line of the input contains an integer t ( 1 ≤ t ≤ 100 ) which denotes the number of test cases to follow.
For each test case, the first line contains n ( number of vectors in the set) . n lines follow, each containing a pair of space separated integers a and b which denote the vector(a,b).

Output

Output should contain exactly t lines, with "YES" or "NO" ( without the quotes - see the sample test case for more details ).

Sample Input

2
3
0 1
-1 0
1 0

4
1 2
10 -6
-5 -1
1 -1

Sample Output

YES
YES

Explanation

Test case 1 : a1 = 0 , a2 = 1, a3 = 1.
Test case 2 : a1 = 2 , a2 = 0 , a3 = 1, a4 = 3.

Date: 2010-09-10
Time limit: 1s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

hmmm

gigsleo @ 24 Sep 2010 11:33 PM

hmmm

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions