5490: I-Smzzl with Safe Zone
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
A boy, whose ID is smzzl, is playing a game named Zig-Zag-Land(ZZL). This is a 2D battle royale game. When the game starts, you will spawn in a random place in the map, and your target is to move into the safe zone.
Given the border of the map and the border of the safe zone, he wants to know the shortest distance between the spawn point and the safe zone in the worst case.
It can be proved that the square of the answer is always rational. In order to check your answer precisely, you need to print the square of your answer modulo 1e9+7. You may find the way to modulo a rational number in Problem link with Grenade .
Given the border of the map and the border of the safe zone, he wants to know the shortest distance between the spawn point and the safe zone in the worst case.
It can be proved that the square of the answer is always rational. In order to check your answer precisely, you need to print the square of your answer modulo 1e9+7. You may find the way to modulo a rational number in Problem li
输入
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤10^4) -- the number of test cases.
For each test case:
In the first line, there is an integer m (3≤m≤10^5), which is the number of vertexes of the safe zone.
In the next m lines, each line contains two integers xi,yi (|xi|,|yi|≤10^7), which is a vertex of the safe zone.
In the next line, there is an integer n (3≤n≤10^5), which is the number of vertexes of the game map.
In the next n lines, each line contains two integers xi,yi (|xi|,|yi|≤10^7), which is a vertex of the game map.
It is guaranteed that:
- The safe zone is a subset of game map.
- The safe zone and the game map are both convex polygons.
- All vertexes are given in counter-clockwise order.
- The sum of n over all test cases will not exceed 10^6.
- The sum of m over all test cases will not exceed 10^6.
You may need to use faster input method.
The first line contains an integer T (1≤T≤10^4) -- the number of test cases.
For each test case:
In the first line, there is an integer m (3≤m≤10^5), which is the number of vertexes of the safe zone.
In the next m lines, each line contains two integers xi,yi (|xi|,|yi|≤10^7), which is a vertex of the safe zone.
In the next line, there is an integer n (3≤n≤10^5), which is the number of vertexes of the game map.
In the next n lines, each line contains two integers xi,yi (|xi|,|yi|≤10^7), which is a vertex of the game map.
It is guaranteed that:
- The safe zone is a subset of game map.
- The safe zone and the game map are both convex polygons.
- All vertexes are given in counter-clockwise order.
- The sum of n over all test cases will not exceed 10^6.
- The sum of m over all test cases will not exceed 10^6.
You may need to use faster input method.
输出
For each test case, output the square of your answer modulo 10^9+7.
样例输入 复制
1
4
0 0
1 0
1 1
0 1
4
-1 -1
2 -1
2 2
-1 2样例输出 复制
2