Code: Star Map

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Point {
    int x, y, id;
    bool operator<(const Point &other) const { return x < other.x; }
};

void solve() {
    int n;
    cin >> n;

    vector<Point> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
        pts[i].id = i + 1;
    }
    sort(pts.begin(), pts.end());

    vector<Point> up;
    vector<Point> down;
    vector<vector<int>> tri;

    for (int i = 0; i < n; i++) {
        Point p = pts[i];

        while (up.size() >= 2) {
            Point top = up.back();
            Point prev = up[up.size() - 2];
            if (top.y > prev.y && top.y > p.y) {
                tri.push_back({prev.id, top.id, p.id});
                up.pop_back();
            } else {
                break;
            }
        }
        up.push_back(p);
        while (down.size() >= 2) {
            Point top = down.back();
            Point prev = down[down.size() - 2];
            if (top.y < prev.y && top.y < p.y) {
                tri.push_back({prev.id, top.id, p.id});
                down.pop_back();
            } else {
                break;
            }
        }
        down.push_back(p);
    }
    cout << tri.size() << "\n";
    for (const auto &tri : tri) {
        cout << tri[0] << " " << tri[1] << " " << tri[2] << "\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}