#P4049. [Cerc2014] Mountainous landscape
[Cerc2014] Mountainous landscape
题目描述
平面上有一条从左向右的折线 ,各点的横坐标严格递增。
对每条线段 (),沿它从 指向 的方向向右延长。请找出最小的 ,使得线段 上至少有一个点严格位于这条射线的上方。点恰好落在射线上时不算在上方。若不存在这样的 ,该线段的答案为 。
输入格式
第一行一个整数 ,表示数据组数。
每组数据第一行一个整数 (),接下来 行,第 行给出两个整数 ,表示顶点 的坐标。保证 ,。
输出格式
每组数据输出一行,共 个空格分隔的整数,依次为第 到第 条线段的答案。
样例
2
8
0 0
3 7
6 2
9 4
11 2
13 3
17 13
20 7
7
0 2
1 2
3 1
4 0
5 2
6 1
7 3
0 3 6 5 6 0 0
6 4 4 0 6 0