Maze

题目描述

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

---

样例输出

5
4

---

提示

【数据规模和约定】
对于5%的数据，满足N = 4。
另外有20%的数据，满足N <= 300，M <= 50。
另外有10%的数据，满足N <= 5 * 10^3，M <= 10^5。
另外有25%的数据，满足N <= 10^5，M <= 300。
对于100%的数据，满足4 <= N <= 10^5，1 <= M <= 10^5，0 <= X,Y <= 10^8。

---

题目来源

zcwwzdjn提供