编程介的小学生 2017-09-28 11:24 采纳率: 20.5%
浏览 782
已采纳

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

  • threenewbee 2017-10-16 01:28
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决