#include #include #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; } // Correct but intentionally slow solution. // // For every circle, collect all angles at which its boundary crosses another // circle or the window boundary. Whether an arc is exposed is constant // between two consecutive angles, so test one midpoint against every circle. // This takes O(K^3) time for a direction containing K circles. namespace { Real normalize_angle(Real angle, Real tau) { while (angle < 0) angle += tau; while (angle >= tau) angle -= tau; return angle; } void add_angle(std::vector& angles, Real angle, Real tau) { angles.push_back(normalize_angle(angle, tau)); } bool is_exposed(const Point& point, int self, const std::vector& circles, i64 X, i64 Y) { if (point.x < 0 || point.x > (Real)X || point.y < 0 || point.y > (Real)Y) { return false; } for (int j = 0; j < (int)circles.size(); ++j) { if (j == self) continue; Real dx = point.x - circles[j].x; Real dy = point.y - circles[j].y; if (dx * dx + dy * dy < (Real)circles[j].r * circles[j].r) { return false; } } return true; } bool is_covered(const Point& point, const std::vector& circles) { for (const Circle& circle : circles) { Real dx = point.x - circle.x; Real dy = point.y - circle.y; if (dx * dx + dy * dy < (Real)circle.r * circle.r) return true; } return false; } Real clipped_circle_union_area_slow(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)); const Real TAU = 2 * PI; Real twice_area = 0; for (int i = 0; i < (int)circles.size(); ++i) { const Circle& circle = circles[i]; std::vector angles{0, TAU}; for (int j = 0; j < (int)circles.size(); ++j) { if (i == j) continue; const Circle& other = circles[j]; Real dx = (Real)other.x - circle.x; Real dy = (Real)other.y - circle.y; Real distance = geo_sqrt(dx * dx + dy * dy); if (distance == 0) continue; Real radius_difference = std::abs((Real)circle.r - other.r); Real radius_sum = (Real)circle.r + other.r; if (!(radius_difference < distance && distance < radius_sum)) continue; Real base = geo_atan2(dy, dx); Real cosine = (distance * distance + (Real)circle.r * circle.r - (Real)other.r * other.r) / (2 * distance * circle.r); Real delta = geo_acos(std::clamp(cosine, Real(-1), Real(1))); add_angle(angles, base - delta, TAU); add_angle(angles, base + delta, TAU); } auto add_vertical_crossings = [&](Real x) { Real cosine = (x - circle.x) / circle.r; if (!(Real(-1) < cosine && cosine < Real(1))) return; Real angle = geo_acos(cosine); add_angle(angles, angle, TAU); add_angle(angles, -angle, TAU); }; auto add_horizontal_crossings = [&](Real y) { Real sine = (y - circle.y) / circle.r; if (!(Real(-1) < sine && sine < Real(1))) return; Real delta = geo_acos(sine); add_angle(angles, PI / 2 - delta, TAU); add_angle(angles, PI / 2 + delta, TAU); }; add_vertical_crossings(0); add_vertical_crossings(X); add_horizontal_crossings(0); add_horizontal_crossings(Y); std::sort(angles.begin(), angles.end()); for (int k = 0; k + 1 < (int)angles.size(); ++k) { Real left = angles[k]; Real right = angles[k + 1]; if (right <= left) continue; Real middle = (left + right) / 2; Point sample{(Real)circle.x + circle.r * geo_cos(middle), (Real)circle.y + circle.r * geo_sin(middle)}; if (!is_exposed(sample, i, circles, X, Y)) continue; Point delta{(Real)circle.r * (geo_cos(right) - geo_cos(left)), (Real)circle.r * (geo_sin(right) - geo_sin(left))}; twice_area += cross(Point{(Real)circle.x, (Real)circle.y}, delta) + (Real)circle.r * circle.r * (right - left); } } // Add covered portions of the rectangle boundary in counterclockwise order. const std::vector vertices{{0, 0}, {(Real)X, 0}, {(Real)X, (Real)Y}, {0, (Real)Y}}; for (int side = 0; side < 4; ++side) { Point from = vertices[side]; Point to = vertices[(side + 1) % 4]; Point direction{to.x - from.x, to.y - from.y}; Real length_squared = direction.x * direction.x + direction.y * direction.y; std::vector positions{0, 1}; for (const Circle& circle : circles) { Real wx = (Real)circle.x - from.x; Real wy = (Real)circle.y - from.y; Real center = (wx * direction.x + wy * direction.y) / length_squared; Real px = from.x + center * direction.x - circle.x; Real py = from.y + center * direction.y - circle.y; Real remaining = (Real)circle.r * circle.r - px * px - py * py; if (remaining <= 0) continue; Real offset = geo_sqrt(remaining / length_squared); Real left = center - offset; Real right = center + offset; if (0 < left && left < 1) positions.push_back(left); if (0 < right && right < 1) positions.push_back(right); } std::sort(positions.begin(), positions.end()); for (int k = 0; k + 1 < (int)positions.size(); ++k) { Real left = positions[k]; Real right = positions[k + 1]; if (right <= left) continue; Real middle = (left + right) / 2; Point sample{from.x + middle * direction.x, from.y + middle * direction.y}; if (!is_covered(sample, circles)) continue; Point p{from.x + left * direction.x, from.y + left * direction.y}; Point q{from.x + right * direction.x, from.y + right * direction.y}; twice_area += cross(p, q); } } Real area = twice_area / 2; Real window = (Real)X * Y; if (area < 0 && area > -1e-7L) area = 0; if (area > window && area < window + 1e-7L) area = window; return area; } } // namespace 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 circle; char direction; std::cin >> circle.x >> circle.y >> circle.r >> direction; (direction == 'V' ? vertical : horizontal).push_back(circle); } Real vertical_area = clipped_circle_union_area_slow(vertical, X, Y); Real horizontal_area = clipped_circle_union_area_slow(horizontal, X, Y); Real window = (Real)X * Y; Real answer = window - (vertical_area + horizontal_area) / 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'; }