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) on the XY-plane and she wants to get to (0,Y)
(1≤X,Y≤106). Unfortunately, N (1≤N≤3⋅105 ) other cows have decided to pose on the X axis. More specifically, cow i will be positioned at (xi,0) with a photographer at (0,yi) where (1≤xi,yi≤106) ready to take their picture. They will begin posing moments before time si (1≤si<T) and they will keep posing for a very long time (they have to get their picture just right). Here, 1≤T≤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 t , she will avoid the line of sights for all photographer/cow pairs that started posing at time si≤t , and let the distance to her final destination be dt. Determine the values of ⌊dt⌋ for each integer t from 0 to T−1 inclusive.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N and T, representing the number of cows posing on the x-axis and the timeframe that Bessie could leave at.
The second line of input contains X and Y, representing Bessie's starting X coordinate and her target Y coordinate respectively.
The next N lines contain si xi and yi . It is guaranteed that all xi are distinct from each other and X, and all yi are distinct from each other and Y. All si will be given in increasing order, where si ≤si +1.
OUTPUT FORMAT (print output to the terminal / stdout):
Print T lines, with the t th (0-indexed) line containing ⌊dt⌋.
SAMPLE INPUT:
4 5
6 7
1 7 5
2 4 4
3 1 6
4 2 9
SAMPLE OUTPUT:
9
9
9
10
12
SAMPLE INPUT:
2 3
10 7
1 2 10
1 9 1
SAMPLE OUTPUT:
12
16
16
For t=0 the answer is 
=12.
For t=1 the answer is 
=16.
SAMPLE INPUT:
5 6
8 9
1 3 5
1 4 1
3 10 7
4 9 2
5 6 6
SAMPLE OUTPUT:
12
12
12
12
14
14
For t=5 the answer is 
. Path: (8,0)→(9,0)→(0,7)→(0,9)
SCORING:
Inputs 4-6: N≤100
Inputs 7-9: N≤3000
Inputs 10-12: T≤10
Inputs 13-18: No additional constraints
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
