18750번 - Ineq 다국어

Given a set of integer pairs S = {(x₁, y₁), . . . ,(x_n, y_n)}, determine if a set of integer triples T = {(a₁, b₁, c₁), . . . ,(a_m, b_m, c_m)} exists such that aixj + biyj < ci for all i and j, and there doesn’t exist an integer pair (x', y') not belonging to S such that a_ix' + b_iy' < c_i for all i.

The first line contains a single integer t (1 ≤ t ≤ 10⁵), denoting the number of test cases.

Each test case is described with an integer n (1 ≤ n ≤ 10⁵), followed by n lines containing two integers x_i and y_i each (−10⁹ ≤ x_i, y_i ≤ 10⁹). All pairs (x_i, y_i) within one test case are distinct.

The sum of n over all test cases does not exceed 10⁵.

For each test case, display a separate line with 1 if the answer is positive, and 0 otherwise.

In the first test case, one possible set of triples is {(1, 0, 1),(0, 1, 1),(−1, 0, 1),(0, −1, 1)}.