http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1502. Maze(王迪)
时间限制:3.0s   内存限制:256.0MB  
总提交次数:105   AC次数:1   平均分:9.48
将本题分享到:
   
 
问题描述
  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。