Untitled
unknown
c_cpp
7 months ago
3.8 kB
2
Indexable
Never
#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; }
Leave a Comment