D06_B Mountainous Landscape

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#pragma warning (disable : 4996)

vector<int> ans;
typedef pair<long long, long long> point;
vector<point> vp;
int n;

#define EPS 1e-6

//cross product of (ab), (cd)
long long cross(point a, point b, point c, point d) {
    point ab = { b.first - a.first, b.second - a.second };
    point cd = { d.first - c.first, d.second - c.second };
    return ab.first * cd.second - ab.second * cd.first;
}

int sign(long long val) {
    return (val == 0 ? 0 : (val < 0 ? -1 : 1));
}

point operator - (point & a, point & b) {
    point r = { b.first - a.first, b.second - a.second };
    return r;
}

//segment tree of convex hulls
struct tree {
    vector<vector<point>> data;
    int n;
    tree() {}
    tree(int n, vector<point> & v) : n(n) {
        data.resize(n * 8 + 100);
        build(v);
    }
    void build(vector<point> & v) {
        build(v, 0, 0, n - 1);
    }
    void build(vector<point> & v, int i, int cl, int cr) {
        if (cl >= cr)
            return;
        if (cl == cr) {
            data[i].push_back(v[cl]);
            return;
        }
        if (cl == cr - 1) {
            data[i].push_back(v[cl]);
            data[i].push_back(v[cr]);
            return;
        }
        for (int j = cl; j <= cr; j++) {
            int t;
            while (t = data[i].size(), t > 1 && (cross(data[i][t - 2], v[j], data[i][t - 2], data[i][t - 1]) < 0))
                data[i].pop_back();
            data[i].push_back(v[j]);
        }
        int m = (cl + cr) >> 1;
        build(v, i * 2 + 1, cl, m);
        build(v, i * 2 + 2, m, cr);
    }
    bool ok(point a, point b, point c, point d) {
        point ab = b - a;
        point ac = c - a;
        point ad = d - a;
        if (cross(a, b, a, c) <= 0 && cross(a, b, a, d) > 0)
            return true;
        return false;
    }
    int get_ans(int i, int cl, int cr, point a, point b, int l, int r) {
        if (r < cl || l > cr)
            return -1;
        if (cl > cr || l > r)
            return -1;
        if (cl == cr - 1) {
            if (ok(a, b, vp[cl], vp[cr])) {
                return cl;
            }
            else {
                return -1;
            }
        }
        int m = (cl + cr) >> 1;
        if (cl >= l && cr <= r) {
            if (can_see(a, b, data[2 * i + 1], l)) {
                int t = get_ans(2 * i + 1, cl, m, a, b, l, min(r, m));
                if (t != -1)
                    return t;
            }
            if (can_see(a, b, data[2 * i + 2], l)) {
                return get_ans(2 * i + 2, m, cr, a, b, max(l, m), r);
            }
        }
        else {
            if (l <= m) {
                int t = get_ans(2 * i + 1, cl, m, a, b, l, min(r, m));
                if (t != -1)
                    return t;
            }
            if (r >= m) {
                int t = get_ans(2 * i + 2, m, cr, a, b, max(l, m), r);
                if (t != -1)
                    return t;
            }
            return -1;
        }
        return -1;
    }
    int get_ans(int i) {
        int ans = -1;
        ans = get_ans(0, 0, n - 1, vp[i], vp[i + 1], i + 2, n - 1);
        return ans;
    }
    bool can_see(point a, point b, vector<point> const & v, int k) {
        if (v.size() == 1)
            return false;
        int st, fin;
        int l = 0, r = v.size() - 1;
        while (l < r && v[l].first < vp[k - 1].first)
            l++;
        if (l == r)
            return false;
        st = l, fin = r;
        double ang = atan2(b.second - a.second, b.first - a.first);
        double last_ang = atan2(v[r].second - v[r - 1].second, v[r].first - v[r - 1].first);
        double first_ang = atan2(v[l + 1].second - v[l].second, v[l + 1].first - v[l].first);
        if (last_ang >= ang || first_ang <= ang) {
            int x1 = sign(cross(a, b, a, v[l]));
            int x2 = sign(cross(a, b, a, v[r]));
            return (x1 <= 0 && x2 > 0);
        }
        while (l < r - 1) {
            int m = (l + r) >> 1;
            double cang = atan2(v[m + 1].second - v[m].second, v[m + 1].first - v[m].first);
            if (cang < ang || abs(cang - ang) < EPS)
                r = m;
            else
                l = m;
        }
        int x1 = min(sign(cross(a, b, a, v[st])), sign(cross(a, b, a, v[fin])));
        int x2 = sign(cross(a, b, a, v[r]));
        return (x1 <= 0 && x2 > 0);
    }
};

tree tr;

void solve() {
    //when next segment is visible
    for (int j = n - 3; j >= 0; j--) {
        if (cross(vp[j], vp[j+1], vp[j+1], vp[j + 2]) > 0) {
            ans[j] = j + 1;
        }
    }
    tr = tree(n, vp);
    for (int j = n - 3; j >= 0; j--) {
        if (ans[j] == -1) {
            int e = tr.get_ans(j);
            ans[j] = e;
        }
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int T;
    cin >> T;
    while (T--) {
        cerr << T << endl;
        cin >> n;
        vp.resize(n);
        ans.assign(n - 1, -1);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &vp[i].first, &vp[i].second);
        }
        solve();
        for (int i = 0; i < n - 1; i++) {
            printf("%d ", ans[i] + 1);
        }
        printf("\n");
    }
    return 0;
}