시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.75 초 (추가 시간 없음) | 1024 MB | 8 | 2 | 2 | 25.000% |
Help the bird Faby to navigate through a sequence of $n$ pairs of pipes, by finding the shortest line he can fly on to reach his destination. For simplicity, we represent Faby as a single point in the plane and assume every pipe has width zero. This way, the gap between every pair of pipes can be represented as an interval on the $y$ axis. The bird starts out at $s = (x_s, y_s)$ and his goal is to reach $t = (x_t, y_t)$. Find the shortest line from $s$ to $t$, passing through all intervals in between in increasing order of their $x$ coordinates.
Figure F.1: Visualisation of the second sample input. The red lines represent the intervals and the black line the shortest possible path. Faby and the black dots are the points in the output. Note that $(2, 1)$ can optionally be included in the output too.
The input consists of:
It can be assumed that $x_s < x_1 < \dots < x_n < x_t$.
Output a sequence of $k$ $(2 \le k \le n+2$) points $p_1, \dots, p_k$, one per line, such that:
If there are multiple valid solutions, you may output any one of them.
0 0 10 0 1 5 -10 10
0 0 10 0
0 0 10 0 4 2 1 3 4 2 3 7 0 2 9 -2 -1
0 0 4 2 9 -1 10 0
ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2021 F번