Photo Op

题目描述

Farmer John 的农场里植被茂盛，每头奶牛都想拍一张展现自然之美的照片。不幸的是，Bessie 还有别的事情要做，但她不想破坏任何拍照。 Bessie 当前站在 XY 平面上的 $(X,0)$，她想走到 $(0,Y)$（$1\le X,Y\le 10^6$）。不幸的是，有 $N$（$1 \leq N \leq 3 \cdot 10^5$）头其他奶牛决定在 $X$ 轴上摆拍。更具体地说，奶牛 $i$ 位于 $(x_i,0)$，其摄影师位于 $(0,y_i)$（$(1 \leq x_i,y_i \leq 10^6)$），准备为它们拍照。它们会在时间 $s_i$（$1 \leq s_i < T$）之前不久开始摆拍，并且会摆拍很长时间（它们必须把照片拍到恰到好处）。这里 $1\le T\le N+1$。 Bessie 知道每头奶牛的拍照日程，并且她会以最短的欧几里得距离到达目的地，同时不穿过任何摄影师到其对应奶牛的视线（她的路径由一条或多条线段组成）。 如果 Bessie 在时间 $t$ 出发，她将避开所有在时间 $s_i \le t$ 开始摆拍的摄影师/奶牛对的视线。设此时她到最终目的地的距离为 $d_t$。请对于从 $0$ 到 $T-1$（含端点）的每个整数 $t$，求出 $\lfloor d_t\rfloor$ 的值。

输入格式

第一行输入 $N$ 和 $T$，分别表示在 $x$ 轴上摆拍的奶牛数量以及 Bessie 可能出发的时间范围。 第二行输入 $X$ 和 $Y$，分别表示 Bessie 的起始 $X$ 坐标和目标点的 $Y$ 坐标。 接下来 $N$ 行每行包含 $s_i$、$x_i$、$y_i$。保证所有 $x_i$ 两两不同且都与 $X$ 不同，所有 $y_i$ 两两不同且都与 $Y$ 不同。所有 $s_i$ 按照不递减顺序给出，即 $s_i \leq s_{i+1}$。

输出格式

输出 $T$ 行，第 $t$ 行（从 0 开始编号）输出 $\lfloor d_t\rfloor$。

4 5
6 7
1 7 5
2 4 4
3 1 6
4 2 9

9
9
9
10
12

2 3
10 7
1 2 10
1 9 1

12
16
16

5 6
8 9
1 3 5
1 4 1
3 10 7
4 9 2
5 6 6

12
12
12
12
14
14

提示

对于 $t=0$，答案为 $\lfloor \sqrt{149} \rfloor=12$。 对于 $t=1$，答案为 $\lfloor 14+\sqrt 5\rfloor=16$。 对于 $t=5$，答案为 $\lfloor 1+\sqrt{9^2+7^2}+2\rfloor=14$。路径： $(8,0)\to (9,0)\to (0,7)\to (0,9)$ 评分： 输入 4-6：$N\le 100$ 输入 7-9：$N\le 3000$ 输入 10-12：$T\le 10$ 输入 13-18：无额外限制 题目致谢：Suhas Nagar

标签: USACO|2025|Gold

来源

USACO|2025|Gold