#P4049. [Cerc2014] Mountainous landscape

    ID: 3251 传统题 2000ms 128MiB 尝试: 53 已通过: 18 难度: 7 上传者: 标签>CF2200提高+/省选-凸包单调栈叉积二分查找线段树上二分

[Cerc2014] Mountainous landscape

题目描述

平面上有一条从左向右的折线 P1P2…PnP_1P_2\dots P_n,各点的横坐标严格递增。

对每条线段 PiPi+1P_iP_{i+1}(1≤i<n1\le i<n),沿它从 PiP_i 指向 Pi+1P_{i+1} 的方向向右延长。请找出最小的 j>ij>i,使得线段 PjPj+1P_jP_{j+1} 上至少有一个点严格位于这条射线的上方。点恰好落在射线上时不算在上方。若不存在这样的 jj,该线段的答案为 00。

输入格式

第一行一个整数 TT,表示数据组数。

每组数据第一行一个整数 nn(2≤n≤1052\le n\le10^5),接下来 nn 行,第 ii 行给出两个整数 xi,yix_i,y_i,表示顶点 PiP_i 的坐标。保证 0≤x1<x2<⋯<xn≤1090\le x_1<x_2<\dots<x_n\le10^9,0≤yi≤1090\le y_i\le10^9。

输出格式

每组数据输出一行,共 n−1n-1 个空格分隔的整数,依次为第 11 到第 n−1n-1 条线段的答案。

样例

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

CERC 2014 组委会原题 B