首先对于一个给定的图形，要找到是否存在答案非常简单。。。
只要维护当然图形的凸包，看一下是否有线段在这条直线上方，直接二分即可，单次询问的时间复杂度$O(logn)$
现在用线段树维护凸包，即对于一个区间$[l, r]$，我们维护点$[P_l, P_{r +1}]$形成的凸包
于是每次查询只要在线段树上二分，总复杂度$O(nlogn + nlog^2n)$(建树 + 查询)
/**************************************************************
Problem: 4049
User: rausen
Language: C++
Result: Accepted
Time:5052 ms
Memory:73960 kb
****************************************************************/ #include <cstdio>
#include <vector> using namespace std;
typedef long long ll;
const int N = 1e5 + ; int read(); int n; struct point {
int x, y;
point(int _x, int _y) : x(_x), y(_y) {}
point() {} inline point operator + (const point &p) const {
return point(x + p.x, y + p.y);
}
inline point operator - (const point &p) const {
return point(x - p.x, y - p.y);
}
inline ll operator * (const point &p) const {
return 1ll * x * p.y - 1ll * y * p.x;
} inline void get() {
x = read(), y = read();
} friend inline ll calc(const point &a, const point &b, const point &c) {
return (a - b) * (c - b);
}
} p[N]; struct convex {
vector <point> s; inline void clear() {
s.clear();
}
#define top ((int) s.size() - 1)
inline void insert(const point &p) {
while (top > && calc(p, s[top - ], s[top]) <= ) s.pop_back();
s.push_back(p);
} #define mid (l + r >> 1)
inline bool query(const point &p, const point &q) {
int l = , r = top - ;
while (l < r) {
if (calc(s[mid], p, q) < calc(s[mid + ], p, q)) r = mid;
else l = mid + ;
}
return calc(s[l], p, q) < || calc(s[l + ], p, q) < ;
}
#undef mid
#undef top
}; struct seg {
seg *ls, *rs;
convex c; #define Len (1 << 16)
inline void* operator new(size_t, int f = ) {
static seg mempool[N << ], *c;
if (f) c = mempool;
c -> ls = c -> rs = NULL, c -> c.clear();
return c++;
}
#undef Len #define mid (l + r >> 1)
void build(int l, int r) {
int i;
for (i = l; i <= r + ; ++i) c.insert(p[i]);
if (l == r) return;
(ls = new()seg) -> build(l, mid);
(rs = new()seg) -> build(mid + , r);
} int query(int l, int r, int L, int R, const point &p, const point &q) {
if (R < l || r < L) return ;
if (L <= l && r <= R) {
if (!c.query(p, q)) return ;
if (l == r) return l;
}
int res = ls -> query(l, mid, L, R, p, q);
return res ? res : rs -> query(mid + , r, L, R, p, q);
}
#undef mid
} *T; int main() {
int Tmp, i;
for (Tmp = read(); Tmp; --Tmp) {
n = read();
for (i = ; i <= n; ++i) p[i].get();
(T = new()seg) -> build(, n - );
for (i = ; i < n - ; ++i)
printf("%d ", T -> query(, n - , i + , n - , p[i], p[i + ]));
puts("");
}
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}