Convex II

题目描述

You are given $k$ pairwise disjoint convex polygons on the plane.

Determine whether there exists a point $O$ and $k$ pairwise distinct rays starting from $O$ such that these rays divide the plane into $k$ closed angular regions, and each polygon can be assigned to exactly one of these regions, with no two polygons assigned to the same region.

The regions include their boundary rays. Therefore, it is allowed that a boundary ray passes through vertices or edges of polygons. It is also allowed that vertices of different polygons lie on the same boundary ray.

You only need to decide whether such a point $O$ and such $k$ rays exist.It is guaranteed for $0 \le \epsilon \lt 10^{-6}$, that the answer does not change if the input coordinates modified by $\epsilon$.

输入格式

The first line contains an integer $T$ $(1 \le T \le 20)$, the number of test cases.

For each test case, the first line contains an integer $k$ $(2 \le k \le 20)$, the number of convex polygons.

For each polygon $i$, the first line contains an integer $n_i$ $(3 \le n_i,\ \sum_{i=1}^{k} n_i \le 120)$, the number of vertices of the $i$-th polygon.

Each of the next $n_i$ lines contains two integers $x_{i,j}$ and $y_{i,j}$ $(-10^3 \le x_{i,j}, y_{i,j} \le 10^3)$, the coordinates of the $j$-th vertex of the $i$-th polygon.

The vertices of each polygon are given in counterclockwise order. Each polygon is convex and has positive area. The given polygons are pairwise disjoint.

It is guaranteed that the sum of $\sum n_i$ over all test cases does not exceed $120$.

输出格式

For each test case, output one line.

Output YES if there exists such a point $O$ and such $k$ rays. Otherwise, output NO.

样例输入 #1

3
2
4
-4 -1
-2 -1
-2 1
-4 1
4
2 -1
4 -1
4 1
2 1
4
4
-6 3
-2 4
-3 15
-7 14
4
-1 -3
10 -2
9 3
-2 2
4
2 -11
3 -11
4 -7
1 -8
4
4 -10
15 -9
14 -8
5 -8
4
4
-8 -8
-6 -8
-6 -6
-8 -6
4
6 -8
8 -8
8 -6
6 -6
4
6 6
8 6
8 8
6 8
4
-8 6
-6 6
-6 8
-8 8

样例输出 #1

YES
NO
YES