1ay 1D。
这是一个跑不过双 \(\log\) 的单 \(\log\) 做法。
考虑双 \(\log\) 做法是怎么做的。令 \(a_i(1\le i\le n)\) 为给定的 \(x\) 坐标递增的点序列，开一棵线段树维护区间上凸壳，第 \(i\) 次查询相当于在 \([i+2,n]\) 区间组成的点的上凸壳中，找到一个在经过 \(a_i,a_{i+1}\) 两点的直线上的点 \(a_j\)，那么线段 \(a_{j-1},a_j\) 就是答案。
这个过程显然可以 \(O(n\log n)\) 预处理之后，线段树上二分实现。复杂度 \(O(n\log^2 n)\)，因为每次查询都要二分斜率所以是双 \(\log\) 的。
有一个避免二分的做法。考虑对 \(i=1,2,\cdots, n-2\) 的询问直线 \(a_i,a_{i+1}\) 离线下来并按照斜率从大到小排序。那么每次在线段树节点中查询的斜率是单调递增的，于是记录一个 \(p_x\) 表示当前斜率下查询 \(x\) 的切点位置即可。
由于线段树节点凸壳点数是 \(O(n\log n)\) 的，所以 \(p_x\) 的总移动次数是 \(O(n\log n)\) 的，所以复杂度是 \(O(n\log n)\) 的。但是实测跑得没有二分快，可能是因为 \(p_x\) 的移动次数卡得比较满。