CRB and Farm

Time Limit
5s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/1)
Description:

CRB has a farm. His farm has a shape of convex polygon. There are K barns in the farm. All of them are strictly inside the polygon. CRB wants to build a fence enclosing all the barns. He prepared 2K posts and steel strips of exactly the same length with the perimeter of his farm. A post can only be placed on the vertex of the polygon(farm), and steel strips must enclose all posts. Now, CRB wonders whether he can build a fence with currently available resources or not. Can you help him?

Input:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer N – the number of vertices of the convex polygon(the shape of CRB‘s farm).
Then N lines follow, i-th line containing two integers x and y, the coordinates of i-th vertex. The vertices are given in counter-clockwise order.
The first line contains an integer K – the number of barns.
Each of the next K lines contains two integers x and y, the coordinates of the barn.
1 ≤ T ≤ 9
3 ≤ N, K ≤ 2 * 105
−109 ≤ x, y ≤ 109
All points(including farm vertices and barns) are pairwise different.
It is guaranteed that the barns never all lie on a line.

Output:

For each test case, output “Yes” if it is possible to build a fence, otherwise output “No”.
If possible, output a solution in the following format:
On the first line, output an integer M - the number of posts used to build a fence.
On the next line, you should output the indices of the vertices(1-based) where you place posts in increasing order.
Your solution will be accepted if M ≤ 2K and the length of the fence is not longer than the perimeter of the farm. Also, the barns must be strictly inside the fence.

Sample Input:
1
5
0 1
3 0
4 2
2 3
0 3
3	
2 1
3 1
3 2
Sample Output:
Yes
4
1 2 3 4
Source:

2015 Multi-University Training Contest 10

Submit