#P16319. [Ucpc2023]Efficient Transportation

[Ucpc2023]Efficient Transportation

题目描述

一个新建工厂在虚拟现实中表示为一个 RR 行 CC 列的矩形网格,共有 R×CR\times C 个正方形区域。

其中有 KK 个区域已经安装了设备。任何移动路径都不能经过这些区域的内部或边界。

现在要把位于第 11 行第 11 列区域中的零件,移动到第 RR 行第 CC 列区域中。为了提高效率,移动路径必须是一条直线段。

你可以在 (1,1)(1,1) 区域的内部或边界上任意选择起点,也可以在 (R,C)(R,C) 区域的内部或边界上任意选择终点。

请判断是否存在一条从起点到终点的直线段,使其不经过任何安装了设备的区域的内部或边界。

输入格式

第一行包含三个整数 R,C,KR,C,K,分别表示网格的行数、列数和障碍区域数量。

2≤R,C≤1000,1≤K≤100000.2\le R,C\le 1000, \qquad 1\le K\le 100000.

接下来 KK 行,每行包含两个整数 r,cr,c,表示第 rr 行第 cc 列的区域安装了设备。

1≤r≤R,1≤c≤C.1\le r\le R, \qquad 1\le c\le C.

保证:

  • (1,1)(1,1) 和 (R,C)(R,C) 不会安装设备;
  • 所有障碍区域坐标互不相同。

输出格式

若存在满足条件的直线路径,输出 1;否则输出 0。

样例 1

输入

4 5 2
2 2
3 4

输出

0

样例 1 示意图

样例 2

输入

4 5 2
3 2
2 4

输出

1

样例 2 示意图