Problem 1644. -- [Balkan 2002]Robot

1644: [Balkan 2002]Robot

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

在不久的将来,机器人会在巴尔干信息学奥林匹克竞赛中把快餐传送给参赛者。他们将用一个简单的正方形盘子装所有的食物。不幸的是,厨房通往参赛者休息大厅的路上将会布满多种障碍物,因此,机器人不能搬运任意大小的盘子。你的任务是设计一个程序用来确定提供食物的盘子的最大尺寸。

预想中的机器人将经过的路线应在由平行的墙构成的走廊中,而且走廊只能有90º 拐角。走廊从X轴正方向开始。障碍物是柱子,由点表示,且都在走廊的两墙间。为了使机器人能够通过那条路,盘子不能碰到柱子或墙——只有盘子的边缘能“靠”到他们。机器人和他的盘子只能在X轴或Y轴方向平移。假定机器人的尺寸小于盘子尺寸且机器人一直完全处于盘子下方。

Input

第一行是一个整数m (1 ≤ m ≤ 30),代表一堵墙有多少水平或竖直的段组成。在输入文件的下面m+1行是“上部”的墙的所有折点(包括端点)的坐标,也就是起始点有较大的坐标y的虚线。同样地,在下面m+1行是“下部”的墙的所有折点(包括端点)的坐标。输入文件下一行包含代表障碍物个数的整数n (0 ≤ n ≤ 100)。在文件下面n行是障碍物坐标。所有坐标都是绝对值小于32001的整数。

Output

只包含一个整数,表示满足题意的盘子最大边长。

Sample Input

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

HINT

Source

[Submit][Status]