2017-08-18 06:14


  • path
  • parallel
  • less
  • each

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.

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 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
0 10
20 10
20 –25
-10 –25
0 0
10 0
10 –10
-10 -10
15 –15
6 5

Sample Output

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享