F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Smzzl with Safe Zone

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 560    Accepted Submission(s): 81


Problem Description
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 $10^9+7$. You may find the way to modulo a rational number in Problem 1006.
 

Input
The input consists of multiple test cases.

The first line contains an integer $T$ ($1 \leq T \leq 10^4$) -- the number of test cases.

For each test case:

In the first line, there is an integer $m$ ($3 \leq m \leq 10^5$), which is the number of vertexes of the safe zone.

In the next $m$ lines, each line contains two integers $x_i,y_i$ ($|x_i|,|y_i| \leq 10^7$), which is a vertex of the safe zone.

In the next line, there is an integer $n$ ($3 \leq n \leq 10^5$), which is the number of vertexes of the game map.

In the next $n$ lines, each line contains two integers $x_i,y_i$ ($|x_i|,|y_i| \leq 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.
 

Output
For each test case, output the square of your answer modulo $10^9+7$.
 

Sample Input
1 4 0 0 1 0 1 1 0 1 4 -1 -1 2 -1 2 2 -1 2
 

Sample Output
2
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 22:11:05, Gzip enabled