# 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;
}
```