# SCUD Busters! ```cpp= #include <cstdio> #include <cstdint> #include <vector> #include <algorithm> using namespace std; struct x_and_y { int x; int y; x_and_y(): x(0), y(0) {} x_and_y(int _x, int _y): x(_x), y(_y) {} x_and_y vec_to(const x_and_y& _des_p) const { return x_and_y{_des_p.x - x, _des_p.y - y}; } int cross_to(const x_and_y& _des_vec) const { return (x * _des_vec.y) - (_des_vec.x * y); } int len_square() const { return (x * x) + (y * y); } static bool less(const x_and_y& _lhs_vec, const x_and_y& _rhs_vec) { if (_lhs_vec.x == 0 && _lhs_vec.y == 0) return true; if (_rhs_vec.x == 0 && _rhs_vec.y == 0) return false; int l_x_r = _lhs_vec.cross_to(_rhs_vec); if (l_x_r) return (l_x_r > 0); return (_lhs_vec.len_square() < _rhs_vec.len_square()); } }; struct kingdom { vector<x_and_y> wall; bool impacted {false}; kingdom() {} kingdom(int _N) { vector<x_and_y> site(_N); for (auto& XY : site) scanf("%d %d", &XY.x, &XY.y); // p0 : leftmost bottom point x_and_y p0 = site[0]; for (auto& XY : site) if (XY.x <= p0.x && XY.y <= p0.y) p0 = XY; // sort sites by counterclockwise order from p0 sort( site.begin(), site.end(), [&](const x_and_y& p1, const x_and_y& p2) { return x_and_y::less(p0.vec_to(p1), p0.vec_to(p2)); }); // build wall wall.reserve(site.size()); wall.push_back(site[0]); wall.push_back(site[1]); for (int S = 2; S < site.size(); S++) { wall.push_back(site[S]); while (wall.size() >= 3 && wall[wall.size() - 3].vec_to(wall[wall.size() - 2]).cross_to( wall[wall.size() - 2].vec_to(wall[wall.size() - 1])) <= 0) { wall[wall.size() - 2] = wall[wall.size() - 1]; wall.pop_back(); } } } void impact(const x_and_y& _des_p) { if (_des_p.vec_to(wall[wall.size() - 1]).cross_to( _des_p.vec_to(wall[0])) <= 0) return; for (int W = 1; W < wall.size(); W++) if (_des_p.vec_to(wall[W - 1]).cross_to( _des_p.vec_to(wall[W])) <= 0) return; impacted = true; } double area() const { double AREA = 0.5 * wall[wall.size() - 1].cross_to(wall[0]); for (int W = 1; W < wall.size(); W++) AREA += 0.5 * wall[W - 1].cross_to(wall[W]); return AREA; } }; int main() { vector<kingdom> world; int N; for (scanf("%d", &N); N != -1; scanf("%d", &N)) world.emplace_back(N); for (x_and_y SCUD; scanf("%d %d", &SCUD.x, &SCUD.y) != -1;) for (auto& K : world) K.impact(SCUD); double sum_impacted_area = 0; for (const auto& K : world) if (K.impacted) sum_impacted_area += K.area(); printf("%.2lf\n", sum_impacted_area); return 0; } ```