06759. USACO·拍照取景 未做

Farmer John 的农场充满了茂盛的植被，每头奶牛都想拥有一张这里的自然美景的照片。不幸的是，Bessie 还有其他地方要去，但她不想打扰任何摄影活动。

Bessie 目前站在 xy 平面上 $(X,0)$ 处，她想要前往 $(0,Y)$（$1\le X,Y\le 10^6$）。不幸的是，$N$（$1\le N\le 3\cdot 10^5$）头其他奶牛决定在 $x$ 轴上摆姿势。更具体地说，奶牛 $i$ 将位于 $(x_i,0)$，她的摄影师位于 $(0,y_i)$（$1\le x_i,y_i\le 10^6$），准备拍摄她的照片。他们将在时刻 $s_i$（$1\le 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\le s_{i+1}$。

输出 $T$ 行，第 $t$ 行（从 0 开始索引）包含 $\lfloor d_t\rfloor$。

【样例解释】

对于 $t=5$ 答案为 $\lfloor 1+\sqrt{9^2+7^2}+2\rfloor =14$。路径：$(8,0)\to (9,0)\to (0,7)\to (0,9)$。

• 测试点 7-9：$N\le 3000$。

• 测试点 10-12：$T\le 10$。

• 测试点 13-18：没有额外限制。

【数据规模与约定】

• 测试点 4-6：$N\le 100$。

• 测试点 7-9：$N\le 3000$。

• 测试点 10-12：$T\le 10$。

• 测试点 13-18：没有额外限制。

供题：Suhas Nagar