#P3121. Maze
Maze
题目描述
迷宫是平面上一个没有自交、没有孔洞的简单多边形。每条边都与某条坐标轴平行,顶点坐标均为整数。
有 次询问。每次给出起点 和终点 ,两点都在多边形内部或边界上。Wayne 只能沿水平方向或竖直方向行进,每次行进的距离不限。他可以沿多边形边界行走,也可以在内部或边界上转弯,整条路线都必须位于多边形内部或边界上。
请分别求出每次询问中从 到 的最短路程。路程为各段行进距离之和。
输入格式
第一行一个整数 ,表示多边形的顶点数。
接下来 行,每行两个整数 ,依次给出多边形的顶点坐标。顶点按顺时针或逆时针排列,最后一个顶点与第一个顶点相连。
接下来一行一个整数 ,表示询问次数。
再接下来 行,每行四个整数 ,表示起点和终点的坐标。
输出格式
输出 行。每行一个非负整数,表示相应询问的最短路程。答案可能超过 位有符号整数的表示范围。
样例
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
8
2 0
2 2
1 2
1 1
0 1
0 3
3 3
3 0
1
0 1 2 0
5
样例 2 中,一条最短路线是 ,长度为 。
数据范围
- 的数据满足 。
- 另外 的数据满足 ,。
- 另外 的数据满足 ,。
- 另外 的数据满足 ,。
- 全部数据满足 ,。所有顶点和询问点的坐标都是 至 之间的整数。