2676. 「BalticOI 2010」BEARs

题目描述

Infinite City 由无限多个南北和东西双向道路分成了一个个方格。其中一条南北道路被编号为 $0$，且向东编号增加，向西编号减小。同理一条东西道路被编号为 $0$，且向北编号增加，向南编号减小。

每个路口可以用一个有序数对表示，第一个数表示南北道路的编号，第二个数表示东西道路的编号。其中一些交点比较重要，被称作主街道。

一天 Wolf 正在巡逻街道，在 $(A,B)$ 路口处发现了著名的 BEAR 强盗团伙。他听说 BEAR 正准备闯入城市 $(0,0)$ 处的蜂蜜仓库，准备阻止他们。

但他们还没有犯罪，所以 Wolf 不能逮捕他们。但 Wolf 有权在任何一个路口处强行停下他们的车，并将路口周围四条道路中的一条关闭。但他不能关闭和主街道相连的线段。所以 Wolf 决定追赶 BEAR，每当他们到达一个路口时关闭一个道路。BEAR 可以进入路口，但随后他们就不能从被堵住的道路离开。

Wolf 希望使 BEAR 离蜂蜜仓库越远越好。你需要求出最大的距离 $D$ 使得 BEAR 能够到达的所有交点 $(x,y)$ 满足 $\max(\lvert x \rvert , \lvert y \rvert) \ge D$。

输入格式

第一行两个整数 $A, B$（$\lvert A \rvert \le 10^6,\lvert B \rvert \le 10^6$），表示 BEAR 的出发点。

接下来一行一个整数 $N$ ($0 \le N \le 500$)，表示主街道的数量。

接下来 $N$ 行每行有四个整数 $X_1, Y_1, X_2, Y_2$ ($\lvert X_i \rvert \le 10^6,\lvert Y_i \rvert \le 10^6$)，表示路口 $(X_1,Y_1)$ 和路口 $(X_2,Y_2)$ 之间的道路是一条主街道，保证 $X_1 = X_2$ 或 $Y_1 = Y_2$。

输出格式

输出一行一个整数，表示 $D$ 的最大值。

样例

输入

3 3
3
1 0 3 0
0 0 0 3
3 0 3 1

输出

1

解释：BEAR 从 $(3,3)$ 出发，Wolf 可以封锁道路使得 BEAR 无法到达离原点距离小于 $1$ 的地方，所以 $D = 1$。

数据范围

• $\lvert A \rvert, \lvert B \rvert \le 10^6$
• $N \le 500$
• $\lvert X_i \rvert, \lvert Y_i \rvert \le 10^6$
• 保证每条主街道是水平或垂直的线段