USACO 2024 US Open Contest, Bronze

Problem 2: Walking Along a Fence

农夫约翰的$N$头奶牛（$1\leq N\leq10^5$）每天都喜欢绕着围起牧场的栅栏散步。

栅栏由$P$个柱子（$4\leq P\leq2\cdot10^5$，$P$为偶数）组成，每个柱子在FJ农场的地图上是不同的二维点$(x,y)$（$0\leq x,y\leq1000$）。每个柱子通过垂直或水平的线段与相邻的两个柱子相连，所以整个栅栏可以看作是一个多边形，其边与$x$轴或$y$轴平行（最后一个柱子与第一个柱子相连，确保栅栏形成一个封闭的环，包围着牧场）。栅栏多边形是“良好行为”的，即栅栏段仅在其端点处可能重叠，每个柱子恰好与两个栅栏段端点对齐，并且在端点处相交的每两个栅栏段都是垂直的。

每头奶牛在日常散步中有一个首选的起点和终点位置，每个位置都是沿着栅栏的某个点（可能在柱子上，也可能不在）。每头奶牛沿着栅栏散步，从起点位置开始，到终点位置结束。由于栅栏形成一个封闭的环，奶牛可以有两条路线可选。因为奶牛有点懒，每头奶牛会选择绕栅栏较短的方向行走（如果两条路线长度相等，奶牛可以选择任意一个方向）。

确定每头奶牛行走的距离。

输入格式（从终端/标准输入读取）

第一行输入包含$N$和$P$。接下来的$P$行，每行包含两个整数，表示栅栏柱子的位置，按顺时针或逆时针顺序排列。接下来的$N$行，每行包含四个整数$x_1$ $y_1$ $x_2$ $y_2$，表示一头奶牛的起点位置$(x_1,y_1)$和终点位置$(x_2,y_2)$。

输出格式（将输出打印到终端/标准输出）

输出$N$个整数，表示每头奶牛行走的距离。

样例输入

5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0

样例输出

2
3
3
4
4

样例解释

第一头奶牛可以直接从$(0,0)$走到$(0,2)$。 第二头奶牛可以从$(0,2)$走到$(0,0)$，然后走到$(1,0)$。 第四头奶牛有两条长度相等的可能路线：$(1,0)\to(0,0)\to(0,2)\to(1,2)$和$(1,0)\to(2,0)\to(2,2)\to(1,2)$。

评分

• 输入2 - 6：$0\leq x,y\leq100$且$N\leq100$
• 输入7 - 11：无额外限制。

题目来源

Brian Dean