#PU1475. USACO 2025 January Contest, Gold — Problem 3. Photo Op

    ID: 1562 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan25来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2025 January Contest, Gold — Problem 3. Photo Op

USACO 2025 January Contest, Gold — Problem 3. Photo Op

题目描述

Farmer John's farm is full of lush vegetation and every cow wants a photo of its natural beauty. Unfortunately, Bessie still has places to be, but she doesn't want to disrupt any photo ops. Bessie is currently standing at (X,0)(X,0) on the XY-plane and she wants to get to (0,Y)(0,Y) (1≤X,Y≤1061\le X,Y\le 10^6). Unfortunately, NN (1≤N≤3⋅1051 \leq N \leq 3 \cdot 10^5) other cows have decided to pose on the XX axis. More specifically, cow ii will be positioned at (xi,0)(x_i,0) with a photographer at (0,yi)(0,y_i) where (1≤xi,yi≤106)(1 \leq x_i,y_i \leq 10^6) ready to take their picture. They will begin posing moments before time sis_i (1≤si<T1 \leq s_i < T) and they will keep posing for a very long time (they have to get their picture just right). Here, 1≤T≤N+11\le T\le N+1. Bessie knows the schedule for every cow's photo op, and she will take the shortest Euclidean distance to get to her destination, without crossing the line of sight from any photographer to their respective cow (her path will consist of one or more line segments). If Bessie leaves at time tt, she will avoid the line of sights for all photographer/cow pairs that started posing at time si≤ts_i \le t, and let the distance to her final destination be dtd_t. Determine the values of ⌊dt⌋\lfloor d_t\rfloor for each integer tt from 00 to T−1T-1 inclusive.

输入格式

The first line of input contains NN and TT, representing the number of cows posing on the xx-axis and the timeframe that Bessie could leave at. The second line of input contains XX and YY, representing Bessie's starting XX coordinate and her target YY coordinate respectively. The next NN lines contain sis_i xix_i and yiy_i. It is guaranteed that all xix_i are distinct from each other and XX, and all yiy_i are distinct from each other and YY. All sis_i will be given in increasing order, where si≤si+1s_i \leq s_{i+1}.

输出格式

Print TT lines, with the ttth (0-indexed) line containing ⌊dt⌋\lfloor d_t\rfloor.

数据范围

Inputs 4-6: N≤100N\le 100 Inputs 7-9: N≤3000N\le 3000 Inputs 10-12: T≤10T\le 10 Inputs 13-18: No additional constraints Problem credits: Suhas Nagar

样例

样例 1

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

样例 2

2 3
10 7
1 2 10
1 9 1
12
16
16
For $t=0$ the answer is $\lfloor \sqrt{149} \rfloor=12$.
For $t=1$ the answer is $\lfloor 14+\sqrt 5\rfloor=16$.

样例 3

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
For $t=5$ the answer is $\lfloor 1+\sqrt{9^2+7^2}+2\rfloor=14$. Path:
$(8,0)\to (9,0)\to (0,7)\to (0,9)$