Delivery Robot

A delivery robot is an autonomous machine designed to provide delivery services. On many campuses, these robots can offer significant convenience to students.

A delivery robot typically integrates various assistance systems, such as collision avoidance systems. These systems should enable the robot to automatically avoid both static obstacles and other robots. Due to the non-immediate nature of velocity control, collision avoidance systems typically allocate a time interval $\Delta t$. If a collision is predicted to occur within $\Delta t$ at the current velocity, the system adjusts the robot's velocity accordingly, including its speed and direction.

We assume that the velocity can change instantly at the beginning of $\Delta t$ but remains constant throughout $\Delta t$. In this problem, we set $\Delta t=1$, meaning you only need to consider the first $\Delta t=1$ from the initial position, without considering the subsequent process.

We envision the delivery robot as a moving convex polygon on a two-dimensional plane with $n$ vertices, with its initial vertex coordinates given. In addition, there is a stationary convex polygonal obstacle on the plane with $m$ vertices, and its vertex coordinates are also given.

As a developer of the collision avoidance system, you want to conduct $q$ tests, each time setting an initial velocity vector $\bf{v}$ for the robot, and the robot will start from the given initial position. According to the principle of the collision avoidance system, if the robot will collide with the obstacle after traveling for $\Delta t=1$ at the current velocity, the robot's velocity should be changed immediately at the beginning, that is, $\bf{v}$ should be modified to $\bf{v}'$.

Without an upper limit on speed, it is evident that a suitable $\bf{v}'$ must exist to prevent a collision within $\Delta t=1$. Depending on the situation, different strategies can be used to select $\bf{v}'$. The objective of this problem is to choose a $\bf{v}'$ that minimizes the magnitude of the difference between $\bf{v}$ and $\bf{v}'$, i.e. $\bf{v}'=\arg\min_{\bf{u}}\Vert {\bf{v}}-{\bf{u}}\Vert$. The magnitude of a vector ${\bf{v}}=(x,y)$ is defined as $\Vert{\bf{v}}\Vert=\sqrt{x^2+y^2}$.

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

The first line of each test case contains three integers $n,m,q$ ($3 \le n,m,q \le 1000$), indicating the number of vertices of the delivery robot and the obstacle, respectively.

Each of the next $n$ lines contains two integers $x,y$ ($-10^6 \le x,y \le 10^6$), indicating the coordinates of a vertex of the delivery robot. The coordinates are given in counter-clockwise order.

Each of the next $m$ lines contains two integers $x,y$ ($-10^6 \le x,y \le 10^6$), indicating the coordinates of a vertex of the obstacle. The coordinates are given in counter-clockwise order. It is guaranteed that the delivery robot and the obstacle are strictly disjoint.

Each of the next $q$ lines contains two integers $x,y$ ($-10^6 \le x,y \le 10^6$), indicating the initial velocity vector ${\bf{v}}=(x,y)$ of the delivery robot.

It is guaranteed that $\sum n \le 2000$ and $\sum m \le 2000$ and $\sum q \le 5000$ over all test cases.

For each test, output the square of the minimum magnitude of ${\bf{v}}-{\bf{v}}'$, i.e.$\min\Vert{\bf{v}}-{\bf{v}}'\Vert^2$, in a single line. You should output the answer as an irreducible fraction $p/q$, where $p$, $q$ are integers and $q > 0$.

1
4 3 3
-1 -1
-2 -1
-2 -2
-1 -2
0 1
1 0
2 2
1 1
2 2
3 3

0/1
1/2
18/5

You can use __int128 in your C++ code.

2023“钉耙编程”中国大学生算法设计超级联赛（8）