[Cerc2014] Mountainous landscape
时间限制：10s 空间限制：128MB
题目描述
You travel through a scenic landscape consisting mostly of mountains - there are n landmarks(peaks a
nd valleys) on your path. You pause for breath and wonder: which mountain are voucurrently seeing on
the horizon?Formally: you are given a polygonal chain PIP2 - Pn in the plane. The x coordinates of
thepoints are in strictly increasing order. For each segment PiPi+l of this chain, find the smallest
index j > i, for which any point of PjPj+i is visible from PiPi+l (lies strictly above the ravPiPi~+
l ) .
给定一个折线图，按x轴递增的顺序给出。对于每个条line，求出在它之后，且下标最小的line。输出这个下标。
n<=100000
输入格式
The first line of input contains the number of test cases T. The descriptions of the test cases
follow:
The first line of each test case contains an integer 'n (2< = N < 100000) - the number ofvertices on
the chain.Each of the following n lines contains integer coordinates xi, Yi of the vertex Pi (0 < xi
<X2 < ... < Xn≤ 109; 0 < Yi < 10^9).
输出格式
For each test case, output a single line contaimng n - I space-separated integers. These shouldbe th
e smallest indices of chain segments visible to the right, or o when no such segment exists.Problem
B: 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
提示
没有写明提示
题目来源
没有写明来源