#1175773 (C++23) No.3675 偏光板

• 問題: No.3675 偏光板
• ユーザー: 👑 みうね
• 提出日時: 2026-08-08 18:41:41
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,019 ms / 2,000 ms
• コード長: 7,419 bytes
• コンパイル時間: 1,747 ms
• コンパイル使用メモリ: 210,244 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-09-04 22:12:34
• 合計ジャッジ時間: 8,787 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 6
other	AC * 54

ソースコード

#include <iomanip>
#include <iostream>
#include <vector>

#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <tuple>
#include <vector>

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<Circle> 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<std::pair<Real, Real>> 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<std::pair<Real, Real>> 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<Point, 4> 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<std::pair<Real, Real>> 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<Circle> 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';
}