Walking Along a Fence

题目描述

农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 10^5$），它们每天都喜欢沿着围住牧场的栅栏散步。 栅栏由 $P$ 根柱子组成（$4 \leq P \leq 2\cdot 10^5$，$P$ 为偶数），每根柱子的位置是农场地图上的一个不同的二维点 $(x,y)$（$0 \leq x, y \leq 1000$）。每根柱子与相邻的两根柱子由栅栏连接，连接段要么是竖直线段要么是水平线段，因此整个栅栏可以看作一个多边形，其边都与 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)$。 SCORING: Inputs 2-6: $0\le x,y \le 100$ and $N\le 100$ Inputs 7-11: No additional constraints. Problem credits: Brian Dean

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze