USACO 2024 US Open Contest, Silver - Problem 2: Painting Fence Posts

问题描述

Farmer John的$N$头奶牛（$1 \leq N \leq 10^5$）每天都喜欢绕着围牧场的栅栏散步。不幸的是，每当一头奶牛走过一个栅栏柱时，就会蹭到它，这就要求Farmer John定期重新粉刷栅栏柱。

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

每头奶牛每天散步都有一个喜欢的起点和终点位置，它们都是沿着栅栏的某个点（可能在柱子处，也可能不在）。每头奶牛沿着栅栏散步，从起点位置开始，到终点位置结束。由于栅栏形成一个封闭的环，奶牛有两条路线可以选择。因为奶牛有点懒，每头奶牛都会选择绕栅栏较短的方向行走。值得注意的是，这个选择总是很明确——不会有平局！

如果奶牛走过一个栅栏柱，或者该栅栏柱是她散步的起点或终点，那么这头奶牛就会碰到这个栅栏柱。请帮助FJ计算每个栅栏柱每天被碰到的次数，这样他就知道接下来要重新粉刷哪个柱子了。

可以证明，给定所有柱子的位置，栅栏的布局只有一种可能。

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

• 输入的第一行包含$N$和$P$。
• 接下来的$P$行，每行包含两个整数，表示栅栏柱子的位置（顺序任意）。
• 接下来的$N$行，每行包含四个整数$x_1$ $y_1$ $x_2$ $y_2$，表示一头奶牛的起点位置$(x_1, y_1)$和终点位置$(x_2, y_2)$。

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

输出$P$个整数，给出每个栅栏柱被碰到的次数。

示例输入1

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

1
2
2
1

解释

以下柱子通过栅栏段相连：$(3, 1) \leftrightarrow (3, 5) \leftrightarrow (1, 5) \leftrightarrow (1, 1) \leftrightarrow (3, 1)$。 每头奶牛碰到的柱子如下：

• 第2和第4个柱子。
• 第2和第3个柱子。
• 第1和第3个柱子。
• 无柱子。
• 无柱子。

示例输入2

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

示例输出2

1
0
0
0
1
1
1
2

示例输入3

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

示例输出3

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

评分

• 输入4 - 6：$N, P \leq 1000$。
• 输入7 - 9：所有位置满足$0 \leq x, y \leq 1000$。
• 输入10 - 15：无额外限制。

问题提供者：Brian Dean