#P17847. [ONTAK 2021]ZAM
[ONTAK 2021]ZAM
城堡
城堡是一个无孔的简单正交多边形,边全部平行于坐标轴,相邻两条边互相垂直。所有顶点均为整数格点,按逆时针顺序给出。
多边形内部以及边界上,所有沿整数网格线的单位线段都是可以行走的走廊。给出 对起终点,均为多边形内部或边界上的整数格点,求每对点之间沿走廊行走的最短距离。
输入格式
第一行偶数 ,接下来 行,每行给出一个顶点的两个坐标。然后一行 ,再接下来 行,每行 。
输出格式
每个询问输出一行最短距离。
数据范围
,。所有坐标为 内的整数。边界没有自交或自接触。起点和终点不同。
样例
10
9 6
9 2
12 2
12 9
2 9
2 1
8 1
8 3
4 3
4 6
2
11 5 3 1
10 4 10 8
14
4