#P3121. Maze

    ID: 2276 传统题 1000ms 512MiB 尝试: 12 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-计算几何扫描线离线与分治查询排序模拟与实现技巧同时事件分阶段处理排序与序列处理同向双指针树算法LCA树上倍增CF2900zcwwzdjn提供

Maze

题目描述

迷宫是平面上一个没有自交、没有孔洞的简单多边形。每条边都与某条坐标轴平行,顶点坐标均为整数。

有 mm 次询问。每次给出起点 ss 和终点 tt,两点都在多边形内部或边界上。Wayne 只能沿水平方向或竖直方向行进,每次行进的距离不限。他可以沿多边形边界行走,也可以在内部或边界上转弯,整条路线都必须位于多边形内部或边界上。

请分别求出每次询问中从 ss 到 tt 的最短路程。路程为各段行进距离之和。

输入格式

第一行一个整数 nn,表示多边形的顶点数。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,依次给出多边形的顶点坐标。顶点按顺时针或逆时针排列,最后一个顶点与第一个顶点相连。

接下来一行一个整数 mm,表示询问次数。

再接下来 mm 行,每行四个整数 xs,ys,xt,ytx_s,y_s,x_t,y_t,表示起点和终点的坐标。

输出格式

输出 mm 行。每行一个非负整数,表示相应询问的最短路程。答案可能超过 3232 位有符号整数的表示范围。

样例

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 中,一条最短路线是 (0,1)→(0,2)→(2,2)→(2,0)(0,1)\to(0,2)\to(2,2)\to(2,0),长度为 1+2+2=51+2+2=5。

数据范围

  • 5%5\% 的数据满足 n=4n=4。
  • 另外 20%20\% 的数据满足 n≤300n\le300,m≤50m\le50。
  • 另外 10%10\% 的数据满足 n≤5000n\le5000,m≤105m\le10^5。
  • 另外 25%25\% 的数据满足 n≤105n\le10^5,m≤300m\le300。
  • 全部数据满足 4≤n≤1054\le n\le10^5,1≤m≤1051\le m\le10^5。所有顶点和询问点的坐标都是 00 至 10810^8 之间的整数。