问题 B: Delivery Robot
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:3
解决:1
题目描述
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
∆t. If a collision is predicted to occur within ∆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 ∆t but remains constant throughout
∆t. In this problem, we set ∆t = 1, meaning you only need to consider the first ∆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 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
∆t = 1 at the current velocity, the robot’s velocity should be changed immediately at the beginning, that
is, v should be modified to v
0
.
Without an upper limit on speed, it is evident that a suitable v
0 must exist to prevent a collision within
∆t = 1. Depending on the situation, different strategies can be used to select v
0
. The objective of
this problem is to choose a v
0
that minimizes the magnitude of the difference between v and v
0
, i.e.
v
0 = arg minu kv − uk. The magnitude of a vector v = (x, y) is defined as kvk =
p
x
2 + y
2.
输入
The first line contains an integer T (1 ≤ T ≤ 20), indicating the number of test cases.
The first line of each test case contains three integers n, m, q (3 ≤ n, m, q ≤ 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 (−106 ≤ x, y ≤ 106
), 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 (−106 ≤ x, y ≤ 106
), 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 (−106 ≤ x, y ≤ 106
), indicating the initial velocity
vector v = (x, y) of the delivery robot.
It is guaranteed that Pn ≤ 2000 and Pm ≤ 2000 and Pq ≤ 5000 over all test cases.
输出
For each test, output the square of the minimum magnitude of v − v
0
, i.e.min kv − v
0k
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