题目描述

Wayne 喜欢玩游戏，并且时常在游戏中思考怎么玩儿才能使花的时间最少。 某天 Wayne 在玩儿一个最新的游戏，这个游戏类似于走迷宫：游戏设置在一个二维坐标系中，有一个简单多边形，每条边都平行于某一条坐标轴，且顶点坐标都是整数。游戏中有很多轮，每一轮都会给出位于多边形内的起点 $s$ 和终点 $t$，Wayne 每次从 $s$ 点出发，每一步可以选择上下左右四个方向之一，前进任意距离，但不能走出多边形。

因为游戏时间与距离是成正比的，于是 Wayne 就想知道，每一轮所需要走的最短距离。

输入格式

第一行一个正整数 $n$，表示多边形的点数。

接下来 $n$ 行按顺时针或逆时针描述这个多边形，每行两个整数 $x,y$，表示多边形上点的坐标。

接下来一行一个正整数 $m$，表示游戏的轮数。

接下来 $m$ 行每行四个整数表示起点和终点的坐标，即 $xs,ys,xt,yt$。

输出格式

对于每一轮游戏单独输出一行一个非负整数表示所需走的最短距离。

8
0 0
0 2
3 2
3 0
2 0
2 1
1 1
1 0
2
0 2 3 0
0 0 2 0

54

数据规模和约定

对于 $5\%$ 的数据，$n = 4$。

对于 $20\%$ 的数据，$n\le 300$，$m \le 50$。

对于 $10\%$ 的数据，$n \le 5 \times 10^3$，$m \le 10^5$。

对于 $25\%$ 的数据，$n \le 10^5$，$m \le 300$。

对于 $100\%$ 的数据，$4 \le n \le 10^5$，$1 \le m \le 10^5$，$0 \le x,y \le 10^8$。

题目来源

zcwwzdjn提供