CF1860F.Evaluate RBS

You are given $2n$ tuples of values $(a, b, c)$, where $a$ and $b$ are positive integers and $c$ is a bracket '(' or ')'. Exactly $n$ tuples have $c = $'(' and the other $n$ tuples have $c =$ ')'.

You are asked to choose two positive values $x$ and $y$ ($x \gt 0$ and $y \gt 0$; not necessarily integers) and sort the tuples in the increasing value of $a \cdot x + b \cdot y$. If several tuples have the same value, you can place them in any order among themselves.

Is it possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence?

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence.

给你 $2n$ 个三元组 $(a, b, c)$，其中 $a$ 和 $b$ 是正整数，$c$ 是左括号 '(' 或右括号 ')'。恰好有 $n$ 个三元组满足 $c = $ '('，其余 $n$ 个三元组满足 $c = $ ')'。

你需要选择两个正实数 $x$ 和 $y$（即 $x \gt 0$ 且 $y \gt 0$；不一定是整数），并按照 $a \cdot x + b \cdot y$ 的值升序对这些三元组进行排序。若若干三元组的 $a \cdot x + b \cdot y$ 值相等，则它们之间的相对顺序可任意安排。

是否存在这样的 $x$ 和 $y$，使得按上述排序后依次取出各三元组中的括号 $c$，所构成的括号序列是一个合法括号序列（regular bracket sequence）？

一个合法括号序列是指：通过在该序列的原始字符之间插入字符 "1" 和 "+"，可将其转化为一个正确的算术表达式。

The first line contains a single integer $t$ ($1 \le t \le 1500$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 1500$).

The $i$-th of the next $2n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^6$) and a character $c_i$ ($c_i = $'(' or $c_i = $')'). Exactly $n$ tuples have $c_i = $'(' and the other $n$ tuples have $c_i =$ ')'.

The sum of $n$ over all testcases doesn't exceed $1500$.

第一行包含一个整数 $t$（$1 \le t \le 1500$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 1500$）。

接下来的 $2n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^6$）以及一个字符 $c_i$（$c_i = $'(' 或 $c_i = $')'）。其中恰好有 $n$ 个元组满足 $c_i = $'('，其余 $n$ 个元组满足 $c_i = $')'。

所有测试用例的 $n$ 值之和不超过 $1500$。

For each testcase, print "YES" if it's possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence. Otherwise, print "NO".

对于每个测试用例，如果存在满足条件的 $x$ 和 $y$，使得按最终顺序从元组中取出括号 $c$ 能构成一个合法括号序列，则输出 "YES"；否则输出 "NO"。

In the first testcase, you can choose $x = 10, y = 0.1$. The values for tuples will be $10 \cdot 1 + 0.1 \cdot 4 = 10.4$ and $10 \cdot 2 + 0.1 \cdot 3 = 20.3$. Thus, the first tuple will go first, then the second one, making the bracket sequence "()", which is regular.

In the second testcase, you can't choose positive $x$ and $y$ such that the opening brackets gets assigned a value less or equal to the value of the closing bracket.

In the fourth testcase, you can choose $x = 0.6, y = 0.55$. The bracket sequence is "(()(()))".

在第一个测试用例中，你可以选择 $x = 10, y = 0.1$。两个元组的值分别为 $10 \cdot 1 + 0.1 \cdot 4 = 10.4$ 和 $10 \cdot 2 + 0.1 \cdot 3 = 20.3$。因此，第一个元组排在前面，第二个元组排在后面，得到括号序列 "()"，该序列是合法的（regular）。

在第二个测试用例中，你无法选择正数 $x$ 和 $y$，使得左括号所对应的值小于或等于右括号所对应的值。

在第四个测试用例中，你可以选择 $x = 0.6, y = 0.55$。括号序列为 "(()(()))"。