34653번 - Freedom Dive 다국어

On a scenic coastline, there are $N$ skyscrapers arranged in a line. For each building $i$ (from $1$ to $N$), we know its distance from the sea, $L_i$, and its height, $H_i$. We can model the top of each building as a point in a 2D plane at coordinates $(L_i, H_i)$. The buildings are sorted by their distance from the sea, so it's guaranteed that $L_i < L_{i+1}$ for all $1 \le i < N$.

You are a professional skydiver and have planned a spectacular dive for $Q$ different days. On the $i$-th day ($1 \le i \le Q$), you are given a planned dive location, which is a horizontal coordinate $d_i$. It is guaranteed that no building is located exactly at $d_i$.

To prepare for the $i$-th day's dive, you must perform the following setup:

• First, choose two buildings: one building $l$ located to the left of your dive location (where $L_l < d_i$) and one building $r$ located to the right (where $L_r > d_i$). It is guaranteed that such a pair of buildings always exists.
• Next, connect the tops of these two buildings, i.e., points $(L_l, H_l)$ and $(L_r, H_r)$, with a straight rope.
• Finally, you will make your jump from the point on this rope that is precisely at the horizontal coordinate $d_i$.

Being a cautious professional, you want to minimize the risk associated with high altitudes. Therefore, for each dive, you must choose the pair of buildings $(l, r)$ that results in the lowest possible altitude for the rope at your jump-off coordinate $d_i$.

Note that the rope is an idealized line segment. It is allowed to pass through or intersect with other buildings; its path is determined only by the two chosen endpoints.

For each of the $Q$ planned dives, find this minimum possible altitude.

The first line contains a single integer $N$ — the number of buildings.

The next $N$ lines describe the buildings. The $i$-th of these lines contains two integers, $L_i$ and $H_i$ — the distance from the sea and the height of the $i$-th building. It is guaranteed that $L_1 < L_2 < \dots < L_N$.

The next line contains a single integer $Q$ — the number of planned diving days.

The next $Q$ lines describe the planned dives. The $i$-th of these lines contains a single integer $d_i$ — the horizontal coordinate for that day's dive. It is guaranteed that $d$ will not be equal to any $L_i$.

For each of the $Q$ dives, output a single line containing two space-separated integers, $s$ and $t$. These two integers must represent the minimum possible starting altitude as an irreducible fraction $s/t$. If the denominator is $1$, you should still print it.

• $2 \le N \le 2 \cdot 10^5$
• $1 \le Q \le 2 \cdot 10^5$
• $1 \le L_i, H_i \le 10^9$
• $L_1 < d_i < L_N$ ($ 1 \le i \le Q$)