레이팅 미적용농부 존의 농장은 무성한 초목으로 가득해서 모든 소가 그 자연의 아름다움을 담은 사진을 원한다. 안타깝게도 베시는 가야 할 곳이 있지만, 어떤 사진 촬영도 방해하고 싶지 않다.
베시는 현재 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\)이다.
베시는 모든 소의 사진 촬영 일정을 알고 있으며, 어떤 사진사와 그 소 사이의 시야선도 가로지르지 않으면서 목적지까지 유클리드 거리가 가장 짧은 경로로 이동한다(경로는 하나 이상의 선분으로 이루어진다).
베시가 시각 \(t\)에 출발하면, \(s_i \le t\)인 시각에 포즈를 취하기 시작한 모든 사진사/소 쌍의 시야선을 피해야 하며, 이때 최종 목적지까지의 거리를 \(d_t\)라고 하자. \(0\)부터 \(T-1\)까지(양 끝 포함)의 각 정수 \(t\)에 대해 \(\lfloor d_t\rfloor\)의 값을 구하시오.
Problem credits: Suhas Nagar
배점
- 입력 4-6: \(N\le 100\)
- 입력 7-9: \(N\le 3000\)
- 입력 10-12: \(T\le 10\)
- 입력 13-18: 추가 제약이 없다
Problem credits: Suhas Nagar
첫째 줄에 \(x\)축 위에서 포즈를 취하는 소의 수와 베시가 출발할 수 있는 시간 범위를 나타내는 \(N\)과 \(T\)가 주어진다.
둘째 줄에 베시의 시작 \(X\) 좌표와 목표 \(Y\) 좌표를 나타내는 \(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 99
9
9
10
122 3
10 7
1 2 10
1 9 112
16
16For \(t=0\) the answer is \(\lfloor \sqrt{149} \rfloor=12\).
For \(t=1\) the answer is \(\lfloor 14+\sqrt 5\rfloor=16\).
5 6
8 9
1 3 5
1 4 1
3 10 7
4 9 2
5 6 612
12
12
12
14
14For \(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)\)