Painting Fence Posts

题目描述

注意：本题的时间限制和内存限制分别为 3s 和 512MB，分别是正常值的 1.5 倍和 2 倍。 农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 10^5$），每头奶牛每天都喜欢沿着围住牧场的栅栏散步。不幸的是，每当奶牛经过一个栅栏柱子时，都会蹭到它，这导致农夫约翰需要经常给栅栏柱子重新刷漆。

栅栏由 $P$ 根柱子组成（$4 \leq P \leq 2\cdot 10^5$，$P$ 为偶数），每根柱子的位置都是农场地图上的一个不同的二维点 $(x,y)$（$0 \leq x, y \leq 10^9$）。每根柱子与相邻的两根柱子由栅栏相连，这些栅栏段要么是竖直线段，要么是水平线段，因此整个栅栏可以视为一个多边形，其边均与 x 轴或 y 轴平行（最后一根柱子会连接回第一根柱子，保证栅栏形成一条封闭环并围住牧场）。该栅栏多边形是“良好”的：栅栏段只可能在端点处重合；每根柱子恰好对应两条栅栏段的端点；并且任意两条在同一端点相接的栅栏段互相垂直。

每头奶牛都有其每日散步的起点和终点，二者都是位于栅栏上的点（可能在柱子上，也可能不在）。奶牛沿着栅栏行走，从起点走到终点。由于栅栏是一条封闭环，奶牛有两条可选路线。因为奶牛有些懒，每头奶牛都会选择沿栅栏方向更短的那条路线。而且这种选择总是唯一明确的——不会出现长度相同的平局。

若奶牛行走时经过某根柱子，或该柱子恰好是她行走的起点或终点，则称奶牛“触碰”了这根柱子。请帮助农夫约翰计算每根栅栏柱子每天被触碰的次数，以便他知道下一次该给哪根柱子刷漆。

可以证明，在给定所有柱子位置的情况下，栅栏的连接方式恰好只有一种可能。

输入格式

第一行输入包含 $N$ 和 $P$。 接下来的 $P$ 行，每行包含两个整数，表示一根栅栏柱子的位置；这些柱子的输入顺序不固定。 接下来的 $N$ 行，每行包含四个整数 $x_1$ $y_1$ $x_2$ $y_2$，表示一头奶牛的起点 $(x_1, y_1)$ 和终点 $(x_2, y_2)$。

输出格式

输出 $P$ 个整数，表示每根栅栏柱子被触碰的次数。

5 4
3 1
1 5
3 5
1 1
2 1 1 5
1 5 3 4
3 1 3 5
2 1 2 1
3 2 3 3

1
2
2
1

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

1
0
0
0
1
1
1
2

1 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 2

1
1
1
1
1
0
0
0
0
0
0
0

提示

以下柱子由栅栏段连接：

$$(3,1)\leftrightarrow (3, 5) \leftrightarrow (1,5) \leftrightarrow (1,1) \leftrightarrow (3,1)$$

每头奶牛触碰到的柱子如下： 柱子 $2$ 和 $4$。 柱子 $2$ 和 $3$。 柱子 $1$ 和 $3$。 没有柱子。 没有柱子。 SCORING: 输入 4-6：$N,P\le 1000$ 输入 7-9：所有位置满足 $0\le x, y\le 1000$。 输入 10-15：无额外限制。 题目作者：Brian Dean

标签: USACO|2024|Silver

来源

USACO|2024|Silver