#3121. Maze

内存限制:128 MiB 时间限制:20 Sec

题目描述

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。