406048: GYM102222 J Nested Triangles

Jamilah is obsessed with nested triangles which share a common edge. Now she selects two points $$$P$$$ and $$$Q$$$ in the plane and calls them pivots. She also provides several other points $$$A_1,A_2,\cdots,A_{n-1}$$$ and $$$A_n$$$, none of which is lying on the line passing through the points $$$P$$$ and $$$Q$$$.

As the one with the same interest, you are asked to find the largest size of a group of nested triangles, and a feasible solution of the largest group with the smallest lexicographical order.

A group of nested triangles, with pivots $$$P$$$ and $$$Q$$$, is a list of selected points provided by Jamilah, denoted by $$$A_{v_1},A_{v_2},\cdots,A_{v_k}$$$, such that for any $$$i \ge 2$$$ the point $$$A_{v_i}$$$ is located inside the triangle $$$PQA_{v_{i-1}}$$$, excluding the border.

The solution $$$v_1,v_2,\cdots,v_k$$$ is the one with the smallest lexicographical order if, for any other feasible solution $$$u_1,u_2,\cdots,u_k$$$, $$$v_1 < u_1$$$ or there exists an integer $$$i~(1\le i < k)$$$ such that $$$v_1=u_1,v_2=u_2,\cdots,v_i=u_i$$$ but $$$v_{i+1}<u_{i+1}$$$.

The input contains several test cases, and the first line is a positive integer $$$T$$$ indicating the number of test cases which is up to $$$1000$$$.

For each test case, the first line contains four integers $$$x_P,y_P,x_Q,y_Q$$$, which are the coordinates of points $$$P$$$ and $$$Q$$$ respectively. The second line contains an integer $$$n~(1 \le n \le 10^5)$$$, which is the number of other points provided by Jamilah. Each of the following $$$n$$$ lines contains two integers, which in the $$$i$$$-th line are the coordinates of point $$$A_i$$$.

We guarantee that all points in a test case are distinct, all coordinates lie in the range of $$$-10^9$$$ to $$$10^9$$$, and the sum of $$$n$$$ in all test cases is up to $$$10^6$$$.

For each test case, output a line containing Case #x: y at first, where x is the test case number starting from $$$1$$$, and y is the size of the largest group of nested triangles. Each of the following $$$y$$$ lines contains an integer, which in the $$$i$$$-th line is the integer $$$v_i$$$.

3
0 0 10 0
6
5 1
5 2
5 3
6 4
6 5
6 6
0 0 10 10
9
1 6
2 3
4 7
6 8
8 2
9 3
7 6
2 4
2 7
0 10 10 0
9
0 0
0 2
2 0
0 4
4 0
0 6
6 0
0 8
8 0

Case #1: 6
6
5
4
3
2
1
Case #2: 3
1
3
2
Case #3: 1
1