← 返回题目列表

Codeforces · 406/D

D. 爬山

中文机器翻译题面 查看原题

这个问题与小克里斯无关。相反,它是关于登山者的(克里斯绝对不是其中之一)。

有 n 个山​​丘排列在一条线上,每个山丘都是垂直线段的形式,一个端点在地面上。山丘从左到右编号为 1 到 n。第 i 个山位于位置 xi ,其顶部高度为 yi 。对于每两个小山a和b,如果从b山的山顶可以看到a山的山顶,则它们的山顶由一根绳子连接起来。形式上,如果连接两个山峰顶点的线段不与任何其他山峰相交或接触,则两个山峰的顶部是连接的。使用这些绳索,登山者可以从一座山移动到另一座山。

有 m 队登山者,每队恰好由两名成员组成。第i队的第一名和第二名登山者分别位于第i个和第bi个山头的山顶。他们想在某个山顶见面。现在,两名登山者分别按照以下过程移动:

1. 如果一个登山者位于另一个登山者已经位于或最终将到达的山顶,则前一个登山者留在该山上;
2. 否则,登山者在当前山的右侧选择一座可以通过绳索到达且最右边的山,爬上这座山并继续该过程(登山者也可以攀爬山顶低于当前山的山顶)。

对于每个登山队,确定这对登山者的会合山的编号!

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105),即山的数量。接下来的 n 行描述了山丘。其中第 i 个包含两个空格分隔的整数 xi、yi (1 ≤ xi ≤ 107; 1 ≤ yi ≤ 1011)、第 i 个山的位置和高度。山丘按 xi 的升序排列,即 xi < xj(对于 i < j)。

下一行输入包含一个整数 m (1 ≤ m ≤ 105),即球队数量。接下来的 m 行描述了团队。其中第 i 个包含两个空格分隔的整数 ai,bi (1 ≤ ai, bi ≤ n),即第 i 队登山者所在山头的编号。 ai = bi 是可能的。

输出

在一行中输出 m 个空格分隔的整数,其中第 i 个整数是第 i 个团队成员的会议山编号。

示例

输入 #1

6
1 4
2 1
3 2
4 3
6 4
7 4
3
3 1
5 6
2 3

输出 #1

5 6 3