#include #include #include #include #include #include #include #include #include using i64 = long long; using i128 = __int128_t; #ifdef POLARIZED_WINDOW_REAL_TYPE using Real = POLARIZED_WINDOW_REAL_TYPE; #else using Real = long double; #endif inline Real geo_sqrt(Real x) { using std::sqrt; return sqrt(x); } inline Real geo_acos(Real x) { using std::acos; return acos(x); } inline Real geo_atan2(Real y, Real x) { using std::atan2; return atan2(y, x); } inline Real geo_cos(Real x) { using std::cos; return cos(x); } inline Real geo_sin(Real x) { using std::sin; return sin(x); } struct Point { Real x, y; }; struct Circle { i64 x, y, r; friend bool operator<(const Circle& a, const Circle& b) { return std::tie(a.x, a.y, a.r) < std::tie(b.x, b.y, b.r); } friend bool operator==(const Circle& a, const Circle& b) { return a.x == b.x && a.y == b.y && a.r == b.r; } }; inline Real cross(Point a, Point b) { return a.x * b.y - a.y * b.x; } // Area of [0,X] x [0,Y] intersected with the union of the disks. inline Real clipped_circle_union_area(std::vector circles, i64 X, i64 Y) { std::sort(circles.begin(), circles.end()); circles.erase(std::unique(circles.begin(), circles.end()), circles.end()); const Real PI = geo_acos(Real(-1)), TAU = 2 * PI; Real twice_area = 0; for (int i = 0; i < (int)circles.size(); ++i) { const Circle& c = circles[i]; std::vector> hidden; bool all_hidden = false; // Add the cyclic interval center-half <= theta <= center+half. auto add_cyclic = [&](Real center, Real half) { if (half <= 0) return; if (half >= PI) { all_hidden = true; return; } Real l = center - half, r = center + half; while (l < 0) l += TAU, r += TAU; while (l >= TAU) l -= TAU, r -= TAU; if (r <= TAU) hidden.push_back({l, r}); else { hidden.push_back({l, TAU}); hidden.push_back({0, r - TAU}); } }; // Add angles satisfying cos(theta-center) > k. Endpoints have zero area. auto add_halfplane = [&](Real center, Real k) { if (k <= -1) all_hidden = true; else if (k < 1) add_cyclic(center, geo_acos(std::clamp(k, Real(-1), Real(1)))); }; // Portions outside the four sides of the window. add_halfplane(PI, (Real)c.x / c.r); // x < 0 add_halfplane(0, ((Real)X - c.x) / c.r); // x > X add_halfplane(1.5L * PI, (Real)c.y / c.r); // y < 0 add_halfplane(0.5L * PI, ((Real)Y - c.y) / c.r);// y > Y for (int j = 0; j < (int)circles.size() && !all_hidden; ++j) if (i != j) { const Circle& d = circles[j]; i128 dx = (i128)d.x - c.x, dy = (i128)d.y - c.y; i128 dist2 = dx * dx + dy * dy; i64 sum = c.r + d.r; if (dist2 >= (i128)sum * sum) continue; // disjoint or externally tangent if (d.r >= c.r) { i64 dif = d.r - c.r; if (dist2 <= (i128)dif * dif) { all_hidden = true; break; } } if (c.r > d.r) { i64 dif = c.r - d.r; if (dist2 <= (i128)dif * dif) continue; // d lies inside c } Real dist = geo_sqrt((Real)dist2); Real phi = geo_atan2((Real)(d.y - c.y), (Real)(d.x - c.x)); Real z = (dist * dist + (Real)c.r * c.r - (Real)d.r * d.r) / (2 * dist * c.r); add_cyclic(phi, geo_acos(std::clamp(z, Real(-1), Real(1)))); } if (all_hidden) continue; std::sort(hidden.begin(), hidden.end()); std::vector> merged; for (auto seg : hidden) { if (seg.second <= seg.first) continue; if (merged.empty() || seg.first > merged.back().second) merged.push_back(seg); else merged.back().second = std::max(merged.back().second, seg.second); } // The complement consists exactly of exposed CCW arcs. For an arc // alpha..beta, integral(x dy-y dx) is cross(o,p(beta)-p(alpha))+r^2*dtheta. Real at = 0; auto add_arc = [&](Real a, Real b) { if (b <= a) return; Point delta{(Real)c.r * (geo_cos(b) - geo_cos(a)), (Real)c.r * (geo_sin(b) - geo_sin(a))}; twice_area += cross(Point{(Real)c.x, (Real)c.y}, delta) + (Real)c.r * c.r * (b - a); }; for (auto [l, r] : merged) { add_arc(at, l); at = std::max(at, r); } add_arc(at, TAU); } // Covered portions of the rectangle boundary, traversed counterclockwise. std::array vertex{{{0, 0}, {(Real)X, 0}, {(Real)X, (Real)Y}, {0, (Real)Y}}}; for (int side = 0; side < 4; ++side) { Point a = vertex[side], b = vertex[(side + 1) % 4]; Point v{b.x - a.x, b.y - a.y}; Real len2 = v.x * v.x + v.y * v.y; std::vector> intervals; for (const Circle& c : circles) { Real wx = (Real)c.x - a.x, wy = (Real)c.y - a.y; Real t0 = (wx * v.x + wy * v.y) / len2; Real px = a.x + t0 * v.x - c.x, py = a.y + t0 * v.y - c.y; Real rem = (Real)c.r * c.r - px * px - py * py; if (rem < 0) continue; Real dt = geo_sqrt(std::max((Real)0, rem) / len2); Real l = std::max((Real)0, Real(t0 - dt)); Real r = std::min((Real)1, Real(t0 + dt)); if (l < r) intervals.push_back({l, r}); } std::sort(intervals.begin(), intervals.end()); Real last_l = 0, last_r = 0; bool have = false; auto add_segment = [&](Real l, Real r) { Point p{a.x + l * v.x, a.y + l * v.y}; Point q{a.x + r * v.x, a.y + r * v.y}; twice_area += cross(p, q); }; for (auto [l, r] : intervals) { if (!have) last_l = l, last_r = r, have = true; else if (l > last_r) add_segment(last_l, last_r), last_l = l, last_r = r; else last_r = std::max(last_r, r); } if (have) add_segment(last_l, last_r); } Real area = twice_area / 2; Real window = (Real)X * Y; // Only remove final round-off excursions; geometric classification is not EPS-based. if (area < 0 && area > -1e-7L) area = 0; if (area > window && area < window + 1e-7L) area = window; return area; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); i64 X, Y; int N; if (!(std::cin >> X >> Y >> N)) return 0; std::vector vertical, horizontal; for (int i = 0; i < N; ++i) { Circle c; char d; std::cin >> c.x >> c.y >> c.r >> d; (d == 'V' ? vertical : horizontal).push_back(c); } Real av = clipped_circle_union_area(vertical, X, Y); Real ah = clipped_circle_union_area(horizontal, X, Y); Real window = (Real)X * Y; Real answer = window - (av + ah) / 2; if (answer < 0 && answer > -1e-7L) answer = 0; if (answer > window && answer < window + 1e-7L) answer = window; std::cout << std::fixed << std::setprecision(15) << answer << '\n'; }