Distinct Buttons (Codeforces 1909A)
Tags: Math, implementation

Deemo - Entrance⠀You are located at the point $$$(0, 0)$$$ of an infinite Cartesian plane. You have a controller with $$$4$$$ buttons which can perform one of the following operations:  $$$\texttt{U}$$$: move from $$$(x, y)$$$ to $$$(x, y+1)$$$;  $$$\texttt{R}$$$: move from $$$(x, y)$$$ to $$$(x+1, y)$$$;  $$$\texttt{D}$$$: move from $$$(x, y)$$$ to $$$(x, y-1)$$$;  $$$\texttt{L}$$$: move from $$$(x, y)$$$ to $$$(x-1, y)$$$. Unfortunately, the controller is broken. If you press all the $$$4$$$ buttons (in any order), the controller stops working. It means that, during the whole trip, you can only press at most $$$3$$$ distinct buttons (any number of times, in any order).There are $$$n$$$ special points in the plane, with integer coordinates $$$(x_i, y_i)$$$.Can you visit all the special points (in any order) without breaking the controller?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of special points.Each of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$-100 \leq x_i, y_i \leq 100$$$), which represent the special point $$$(x_i, y_i)$$$.Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output: For each test case, output "YES" (without quotes), if you can reach all the special points without breaking the controller, and "NO" (without quotes) otherwise.You may output each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

Note: In the first test case, you can move as follows:   you start from $$$(0, 0)$$$;  you visit the special point $$$(x_2, y_2) = (0, 0)$$$;  you press $$$\texttt{R}$$$, and you move from $$$(0, 0)$$$ to $$$(1, 0)$$$;  you press $$$\texttt{D}$$$, and you move from $$$(1, 0)$$$ to $$$(1, -1)$$$;  you visit the special point $$$(x_1, y_1) = (1, -1)$$$;  you visit the special point $$$(x_3, y_3) = (1, -1)$$$. Therefore, you can visit all the special points using only the buttons $$$\texttt{R}$$$, $$$\texttt{D}$$$, so the controller does not break.Note that the special points may coincide.In the second test case, you can show that you can visit all the special points using only the buttons $$$\texttt{U}$$$, $$$\texttt{D}$$$, $$$\texttt{L}$$$.In the third test case, you can show that you must press all the buttons ($$$\texttt{U}$$$, $$$\texttt{R}$$$, $$$\texttt{D}$$$, $$$\texttt{L}$$$) to visit all the points, so the controller would break.

Sample Inputs:
6
3
1 -1
0 0
1 -1
4
-3 -2
-3 -1
-3 0
-3 1
4
1 1
-1 -1
1 -1
-1 1
6
-4 14
-9 -13
-14 5
14 15
-8 -4
19 9
6
82 64
39 91
3 46
87 83
74 21
7 25
1
100 -100

Sample Outputs:
YES
YES
NO
NO
YES
YES

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        x_pos = x_neg = y_pos = y_neg = 0
        for _ in range(n):
            (x, y) = map(int, input().split())
            if x < 0:
                x_neg += 1
            elif x > 0:
                x_pos += 1
            if y < 0:
                y_neg += 1
            elif y > 0:
                y_pos += 1
        if x_pos and x_neg and y_pos and y_neg:
            print('NO')
        else:
            print('YES')
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def sol(ct):
    input = sys.stdin.readline
    n = int(input())
    q1 = q2 = q3 = q4 = px = py = nx = ny = False
    for i in range(n):
        (x, y) = tuple(map(int, input().split()))
        if y == 0:
            if x > 0:
                px = True
            if x < 0:
                nx = True
        if x == 0:
            if y < 0:
                ny = True
            if y > 0:
                py = True
        if x > 0:
            if y < 0:
                q4 = True
            if y > 0:
                q1 = True
        if x < 0:
            if y < 0:
                q3 = True
            if y > 0:
                q2 = True
    if not (q1 or q2 or q3 or q4 or px or py or nx or ny):
        print('yes')
    elif not (q3 or q4 or ny) and (q1 or q2 or px or py or nx):
        print('yes')
    elif not (q2 or q1 or py) and (q3 or q4 or px or ny or nx):
        print('yes')
    elif not (q3 or q2 or nx) and (q4 or q1 or px or py or ny):
        print('yes')
    elif not (q1 or q4 or px) and (q3 or q2 or ny or py or nx):
        print('yes')
    else:
        print('no')
for _ in range(int(input())):
    sol(_)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
MOD = 1000000007
input = sys.stdin.readline

def debug(*args):
    print(*args, file=sys.stderr)

def solve():
    n = int(input())
    (c1, c2, c3, c4, up, down, right, left) = (0, 0, 0, 0, 0, 0, 0, 0)
    check_right = False
    check_left = False
    check_up = False
    check_down = False
    for _ in range(n):
        (x, y) = map(int, input().split())
        if y > 0:
            if x > 0:
                c1 += 1
            if x < 0:
                c2 += 1
            if x == 0:
                up += 1
                check_up = True
        if y < 0:
            if x > 0:
                c4 += 1
            if x < 0:
                c3 += 1
            if x == 0:
                check_down = True
                down += 1
        if y == 0:
            if x > 0:
                right += 1
                check_right = True
            if x < 0:
                left += 1
                check_left = True
    if c1 > 0:
        check_right = True
        check_up = True
    if c2 > 0:
        check_left = True
        check_up = True
    if c3 > 0:
        check_down = True
        check_left = True
    if c4 > 0:
        check_right = True
        check_down = True
    l = 0
    if check_down:
        l += 1
    if check_left:
        l += 1
    if check_right:
        l += 1
    if check_up:
        l += 1
    if l == 4:
        print('NO')
    else:
        print('YES')
t = int(sys.stdin.readline().strip())
for _ in range(t):
    solve()