AcWing 5590. 沿栅栏散步

Week 4
3月11日

题目描述

农夫约翰有 $N$ 头奶牛，每头奶牛都喜欢日常沿着包围牧场的栅栏散步。

栅栏由 $P$ 根柱子组成（$P$ 为偶数），每根柱子的位置是农夫约翰农场地图上的一个不同的二维坐标点 $(x,y)$。

每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子，因此整个栅栏可以被视为各边平行于 $x$ 轴或 $y$ 轴的一个多边形（最后一根柱子连回第一根柱子，确保围栏形成一个包围牧场的闭环）。

栅栏多边形是「规则的」，体现在栅栏段仅可能在其端点处重合，每根柱子恰好属于两个栅栏段，同时每两个在端点处相交的栅栏段都是垂直的。

每头奶牛的日常散步都有一个偏好的起始和结束位置，均为沿栅栏的某个点（可能在柱子处，也可能不在）。

每头奶牛日常散步时沿着栅栏行走，从起始位置开始，到结束位置结束。

由于栅栏形成闭环，奶牛有两条路线可以选择。

由于奶牛是一种有点懒的生物，每头奶牛都会选择距离较短的方向沿栅栏行走（如果并列，奶牛可以选择任一方向）。

输入格式

输入的第一行包含 $N$ 和 $P$。

以下 $P$ 行的每一行包含两个整数，以顺时针或逆时针顺序表示栅栏柱子的位置。

以下 $N$ 行的每一行包含四个整数 $x_1,y_1,x_2,y_2$，表示一头奶牛的起始位置 $(x_1,y_1)$ 和结束位置 $(x_2,y_2)$

输出格式

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

数据范围

$1\le N\le 10^5$,
$4\le P\le 2\times 10^5$,
$0\le x,y\le 1000$

输入样例：

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)$。

---

AC_code

python">n,p=map(int,input().split())  
q = []  
for _ in range(p):  x, y = map(int, input().split())  q.append((x, y))  s = [[0] * 1010 for _ in range(1010)]  
sum = 0  
x, y = q[-1]  # 令最后一个柱子的坐标为起点  for i in range(p):  tx, ty = q[i] # 终点  vx = 1 if tx > x else (-1 if tx < x else 0)  vy = 1 if ty > y else (-1 if ty < y else 0)  while x != tx or y != ty:  x += vx  y += vy  sum += 1  s[x][y] = sum  for _ in range(n):  x1, y1, x2, y2 = map(int, input().split())  dis = s[x2][y2] - s[x1][y1]  if dis < 0:  dis += sum  print(min(dis, sum - dis))

---

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢