Untitled

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

class Skyscraper {
public:
    int x, y;
    Skyscraper(int x, int y) : x(x), y(y) {}
};

bool is_intersect(int x1_, int y1_, int x2_, int y2_, int x3_, int y3_, int x4_, int y4_) {
    double x1 = x1_;
    double x2 = x2_;
    double x3 = x3_;
    double x4 = x4_;
    double y1 = y1_;
    double y2 = y2_;
    double y3 = y3_;
    double y4 = y4_;
    //y4 -= 0.0001;
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1));
    return 0 <= ua && ua <= 1 && 0 <= ub && ub <= 1;
}

bool is_intersect_with_skyscraper(const Skyscraper& viewpoint, const Skyscraper& skyscraper_to_see, const Skyscraper& skyscraper_obstacle) {
    return is_intersect(viewpoint.x, viewpoint.y, skyscraper_to_see.x, skyscraper_to_see.y, skyscraper_obstacle.x, 0,
                        skyscraper_obstacle.x, skyscraper_obstacle.y);
}

std::vector<int> get_obstacles(const Skyscraper& viewpoint, const Skyscraper& skyscraper, const std::vector<Skyscraper*>& skyscrapers) {
    std::vector<int> obstacles;
    for (size_t i = 0; i < skyscrapers.size(); ++i) {
        if (skyscrapers[i] == nullptr) continue;
        if (is_intersect_with_skyscraper(viewpoint, skyscraper, *skyscrapers[i])) {
            obstacles.push_back(i);
        }
    }
    return obstacles;
}

int count_visible(const std::vector<std::vector<int>>& obstacles) {
    return std::count_if(obstacles.begin(), obstacles.end(), [](const std::vector<int>& obs) { return obs.empty(); });
}

std::vector<int> solution() {
    int n;
    std::cin >> n;
    int x, y;
    std::cin >> x >> y;
    Skyscraper viewpoint(x, y);
    std::vector<Skyscraper*> skyscrapers;
    for (int i = 0; i < n - 1; ++i) {
        std::cin >> x >> y;
        skyscrapers.push_back(new Skyscraper(x, y));
    }
    std::vector<std::vector<int>> obstacles;
    for (size_t i = 0; i < skyscrapers.size(); ++i) {
        if (skyscrapers[i] != nullptr) {
            std::vector<int> i_obstacles = get_obstacles(viewpoint, *skyscrapers[i], std::vector<Skyscraper*>(skyscrapers.begin(), skyscrapers.begin() + i));
            obstacles.push_back(i_obstacles);
        } else {
            obstacles.emplace_back();
        }
    }
    int visible = count_visible(obstacles);
    std::vector<int> to_break;
    while (count_visible(obstacles) != n - 1) {
        std::set<int> local_to_break;
        for (auto& obstacle : obstacles) {
            if (!obstacle.empty() && std::count(obstacles.begin(), obstacles.end(), obstacle) > obstacle.size()) {
                for (int obs : obstacle) {
                    local_to_break.insert(obs);
                    skyscrapers[obs] = nullptr;
                }
                break;
            }
        }
        if (local_to_break.empty()) {
            return to_break;
        }
        for (auto& obstacle : obstacles) {
            std::vector<int> temp = obstacle;
            for (int i : temp) {
                if (local_to_break.count(i)) {
                    obstacle.erase(std::remove(obstacle.begin(), obstacle.end(), i), obstacle.end());
                }
            }
        }
        int new_visible = count_visible(obstacles);
        if (visible < new_visible) {
            to_break.insert(to_break.end(), local_to_break.begin(), local_to_break.end());
        }
    }
    return to_break;
}

int main() {
    int t;
    std::cin >> t;

    for (int i = 0; i < t; ++i) {
        std::vector<int> ans = solution();
        std::cout << ans.size() << std::endl;
        for (int a : ans) {
            std::cout << a + 2 << ' ';
        }
        std::cout << std::endl;
    }
    return 0;
}