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

• 問題: No.3675 偏光板
• ユーザー: TKTYI
• 提出日時: 2026-09-03 02:21:20
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 923 ms / 2,000 ms
• コード長: 5,391 bytes
• コンパイル時間: 1,318 ms
• コンパイル使用メモリ: 206,336 KB
• 実行使用メモリ: 9,916 KB
• 最終ジャッジ日時: 2026-09-04 23:11:29
• 合計ジャッジ時間: 10,906 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

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

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

#define PI 3.14159265358979323846

using namespace std;

struct Point2D { long double x, y; };
struct Circle { long double x, y, r; };

const long double EPS = 1e-11L;

vector<Point2D> clip_polygon_halfplane(const vector<Point2D>& poly, long double a, long double b, long double c) {
    vector<Point2D> res;
    int n = poly.size();
    if (n == 0) return res;

    long double norm = hypot(a, b);
    if (norm < 1e-12L) {
        if (c >= -1e-12L) return poly; 
        else return {};               
    }
    a /= norm; b /= norm; c /= norm;

    for (int i = 0; i < n; i++) {
        Point2D p1 = poly[i];
        Point2D p2 = poly[(i + 1) % n];
        long double d1 = a * p1.x + b * p1.y + c;
        long double d2 = a * p2.x + b * p2.y + c;

        if (d1 >= 0.0L) {
            res.push_back(p1);
            if (d2 < 0.0L) {
                long double t = max(0.0L, min(1.0L, d1 / (d1 - d2)));
                res.push_back({p1.x + t * (p2.x - p1.x), p1.y + t * (p2.y - p1.y)});
            }
        } else {
            if (d2 >= 0.0L) {
                long double t = max(0.0L, min(1.0L, d1 / (d1 - d2)));
                res.push_back({p1.x + t * (p2.x - p1.x), p1.y + t * (p2.y - p1.y)});
            }
        }
    }
    return res;
}

long double circle_segment_area(Point2D p1, Point2D p2, long double r) {
    long double dx = p2.x - p1.x;
    long double dy = p2.y - p1.y;
    long double a = dx * dx + dy * dy;
    long double b = 2.0L * (p1.x * dx + p1.y * dy);
    long double c = p1.x * p1.x + p1.y * p1.y - r * r;

    vector<long double> ts = {0.0L, 1.0L};
    long double t1 = 2.0L, t2 = 2.0L; 
    bool intersects = false;

    if (a > 1e-13L) {
        long double det = b * b - 4.0L * a * c;
        if (det > 0.0L) {
            long double sq = sqrt(det);
            long double q = (b >= 0.0L) ? -0.5L * (b + sq) : -0.5L * (b - sq);
            t1 = q / a;
            t2 = (q != 0.0L) ? (c / q) : 0.0L;
            if (t1 > t2) swap(t1, t2);
            
            if (t1 > 0.0L && t1 < 1.0L) ts.push_back(t1);
            if (t2 > 0.0L && t2 < 1.0L) ts.push_back(t2);
            intersects = true;
        }
    }
    sort(ts.begin(), ts.end());

    long double area = 0.0L;
    for (size_t i = 0; i < ts.size() - 1; i++) {
        long double ta = ts[i], tb = ts[i+1];
        if (tb - ta < EPS) continue;
        
        Point2D q1 = {p1.x + ta * dx, p1.y + ta * dy};
        Point2D q2 = {p1.x + tb * dx, p1.y + tb * dy};
        
        bool inside = false;
        if (intersects) {
            long double tm = (ta + tb) / 2.0L;
            if (tm > t1 + EPS && tm < t2 - EPS) {
                inside = true;
            }
        }
        
        if (inside) {
            area += 0.5L * (q1.x * q2.y - q1.y * q2.x);
        } else {
            long double cross_prod = q1.x * q2.y - q1.y * q2.x;
            long double dot_prod = q1.x * q2.x + q1.y * q2.y;
            long double dth = atan2(cross_prod, dot_prod);
            area += 0.5L * r * r * dth;
        }
    }
    return area;
}

long double circle_polygon_area(long double cx, long double cy, long double r, const vector<Point2D>& poly) {
    if (poly.size() < 3) return 0.0L;
    long double area = 0.0L;
    for (size_t i = 0; i < poly.size(); i++) {
        Point2D p1 = poly[i];
        Point2D p2 = poly[(i + 1) % poly.size()];
        area += circle_segment_area({p1.x - cx, p1.y - cy}, {p2.x - cx, p2.y - cy}, r);
    }
    return std::abs(area);
}

long double f(long double X, long double Y, vector<Circle> C) {
    vector<Circle> unique_C;
    for (const auto& c : C) {
        bool dup = false;
        for (auto& uc : unique_C) {
            if (std::abs(c.x - uc.x) < 1e-7L && std::abs(c.y - uc.y) < 1e-7L) {
                uc.r = max(uc.r, c.r);
                dup = true;
                break;
            }
        }
        if (!dup) unique_C.push_back(c);
    }
    C = move(unique_C);

    int N = C.size();
    if (N == 0) return 0.0L;

    long double area_sum = 0.0L;

    for (int i = 0; i < N; i++) {
        vector<Point2D> poly = {
            {0.0L, 0.0L},
            {X, 0.0L},
            {X, Y},
            {0.0L, Y}
        };

        for (int j = 0; j < N; j++) {
            if (i == j) continue;

            long double a = 2.0L * (C[i].x - C[j].x);
            long double b = 2.0L * (C[i].y - C[j].y);
            long double c = (C[j].x * C[j].x + C[j].y * C[j].y - C[j].r * C[j].r) -
                            (C[i].x * C[i].x + C[i].y * C[i].y - C[i].r * C[i].r);

            poly = clip_polygon_halfplane(poly, a, b, c);
            if (poly.empty()) break;
        }

        if (poly.size() >= 3) {
            area_sum += circle_polygon_area(C[i].x, C[i].y, C[i].r, poly);
        }
    }

    return area_sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long double X, Y;
    int N;
    if (!(cin >> X >> Y >> N)) return 0;
    vector<Circle> v, h;

    for (int i = 0; i < N; i++) {
        long double x, y, r;
        char d;
        cin >> x >> y >> r >> d;
        (d == 'V' ? v : h).push_back({x, y, r});
    }

    long double ans = X * Y;
    ans -= f(X, Y, v) * 0.5L;
    ans -= f(X, Y, h) * 0.5L;

    cout << fixed << setprecision(20) << (double)ans << "\n";
    return 0;
}