8049: BZOJ4049:[Cerc2014] Mountainous landscape

Memory Limit:128 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: