BZPRO

#1949. [Ceoi2006]Walk

内存限制：162 MiB 时间限制：4 Sec
提交 提交记录 讨论

题目描述

考虑X-Y平面上满足X≥0的整数结点 给定若干个矩形及一个目标点，紧靠每个矩形外部的一周范围内没有其它矩形的点，所有矩形中的所有点满足X≥0 求一条以(0,0)点为起点，以目标点为终点、不与任何矩形相交的最短路径

输入格式

第一行输入为两个整数X与Y(1≤X≤106,-106≤Y≤106)表示目标点坐标 第二行为一个整数N(0≤N≤105)，表示矩形的数目 接下来的N行每行包括4个整数： X1,Y1,X2,Y2(0≤X1,X2≤106,0≤Y1,Y2≤106) 即N个矩形的某对对角顶点。

输出格式

第一行包括一个整数L，表示最短路径长度

样例

样例输入


			
42 33

66

35 37 37 37

13 -41 13 6

40 -2 42 -1

27 -2 28 -2

15 -4 16 2

29 16 29 16

38 -34 38 -11

22 -5 22 -5

34 27 34 35

28 12 29 12

10 11 11 13

11 25 11 25

24 4 25 40

27 9 27 10

27 -4 27 -4

29 7 29 10

3 -13 5 -13

16 17 16 17

18 6 18 48

4 7 4 14

5 2 5 5

40 22 44 32

21 13 21 13

34 3 34 25

41 11 42 20

15 -15 16 -9

24 -46 25 -6

5 -4 5 -3

10 17 11 17

28 14 29 14

3 -15 4 -15

10 15 10 15

16 8 16 9

2 2 2 2

1 -4 3 -3

10 21 10 21

22 8 22 8

20 -3 21 2

10 19 11 19

7 -47 8 3

28 -11 28 -6

20 4 20 9

11 23 11 23

15 -17 16 -17

27 0 27 3

43 5 43 8

15 -7 16 -6

16 -19 16 -19

11 -10 11 -10

21 11 22 11

4 0 4 0

15 5 16 6

3 -11 5 -7

11 -8 11 -1

28 -13 28 -13

21 15 22 15

40 -30 43 -5

41 34 43 35

15 14 16 15

21 -16 22 -13

1 -1 2 -1

10 1 11 9

22 17 22 17

31 -50 32 -1

22 -8 22 -7

16 -21 16 -21

样例输出


			
89

数据范围与提示

BZPRO Powered by Remmina.
Github Repository