编程介的小学生 2017-08-18 06:14 采纳率: 20.5%
浏览 757
已采纳

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条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥50 汇编语言除法溢出问题
  • ¥65 C++实现删除N个数据列表共有的元素
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗