ROBOT

Problem Description
In the near future, robots are going to transport snacks to the contestants at Balkan Olympiads in Informatics. Robot carries all snacks on a single square tray. ≤Unfortunately, path between the kitchen and the contestant hall is expected to be full of various obstacles and, thus, robot won\'t be able to carry a tray of an arbitrary size. It is your task to write a program ZAD1.EXE to determine the size of the largest possible tray that can be used for catering.
The path that the robot is supposed to traverse is contained in the corridor with parallel walls and corridor can have only 90o turns. Corridor starts in the direction of the positive x-axis. Obstacles are pillars, represented as points, and they are all between the walls of the corridor. In order for the robot to be able to traverse the path, the tray must not hit pillars or walls -- it may only \"touch\" them with its side. Robot and his tray move only by translation in the direction of x or y-axis. Assume that the dimensions of the robot are smaller than the dimensions of the tray and that the robot is always completely under the tray.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases.
In the first line of the each test case, is an integer m (1 ≤ m ≤ 30) that represents the number of straight wall segments. In the next m+1 lines of the input file are the x and y coordinates of all turning points (including the endpoints) of the \"upper\" walls, i.e. the broken line whose initial point has a greater y coordinate. Similarly, in the next m+1 lines are the x and y coordinates of all turning points (including the endpoints) of the \"lower\" walls. Next line of the input file contains the integer n (0 ≤ n ≤ 100) that represents the number of obstacles. In the next n lines of the input file are the x and y coordinates of the obstacles. All coordinates are integers with absolute values less than 32001.

Output
Output should contain only one integer for each test case that represents the length of the side of the largest tray that satisfies the conditions of the problem.

Sample Input
1
3
0 10
20 10
20 –25
-10 –25
0 0
10 0
10 –10
-10 -10
2
15 –15
6 5

Sample Output
5

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问