#PU1475. USACO 2025 January Contest, Gold — Problem 3. Photo Op
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 on the XY-plane and she wants to get to (). Unfortunately, () other cows have decided to pose on the axis. More specifically, cow will be positioned at with a photographer at where ready to take their picture. They will begin posing moments before time () and they will keep posing for a very long time (they have to get their picture just right). Here, . 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 , she will avoid the line of sights for all photographer/cow pairs that started posing at time , and let the distance to her final destination be . Determine the values of for each integer from to inclusive.
输入格式
The first line of input contains and , representing the number of cows posing on the -axis and the timeframe that Bessie could leave at. The second line of input contains and , representing Bessie's starting coordinate and her target coordinate respectively. The next lines contain and . It is guaranteed that all are distinct from each other and , and all are distinct from each other and . All will be given in increasing order, where .
输出格式
Print lines, with the th (0-indexed) line containing .
数据范围
Inputs 4-6: Inputs 7-9: Inputs 10-12: 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)$