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

• 問題: No.3675 偏光板
• ユーザー: TKTYI
• 提出日時: 2026-09-03 01:55:47
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: WA
• 実行時間: -
• コード長: 4,774 bytes
• コンパイル時間: 1,310 ms
• コンパイル使用メモリ: 204,796 KB
• 実行使用メモリ: 9,792 KB
• 最終ジャッジ日時: 2026-09-04 23:11:18
• 合計ジャッジ時間: 6,264 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

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

ソースコード

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

#define M_PI 3.14159265358979323846

using namespace std;

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

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

    double norm = hypot(a, b);
    if (norm < 1e-12) return poly; 
    a /= norm; b /= norm; c /= norm;

    auto get_dist = [&](Point2D p) { return a * p.x + b * p.y + c; };

    for (int i = 0; i < n; i++) {
        Point2D p1 = poly[i];
        Point2D p2 = poly[(i + 1) % n];
        double d1 = get_dist(p1);
        double d2 = get_dist(p2);

        if (d1 >= -1e-9) {
            res.push_back(p1);
            if (d2 < -1e-9) {
                double t = d1 / (d1 - d2);
                res.push_back({p1.x + t * (p2.x - p1.x), p1.y + t * (p2.y - p1.y)});
            }
        } else {
            if (d2 >= -1e-9) {
                double t = d1 / (d1 - d2);
                res.push_back({p1.x + t * (p2.x - p1.x), p1.y + t * (p2.y - p1.y)});
            }
        }
    }
    return res;
}

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

    vector<double> ts = {0.0, 1.0};
    if (a > 1e-12) {
        double det = b * b - 4 * a * c;
        if (det > 0) {
            det = sqrt(det);
            double t1 = (-b - det) / (2 * a);
            double t2 = (-b + det) / (2 * a);
            if (t1 > 0 && t1 < 1) ts.push_back(t1);
            if (t2 > 0 && t2 < 1) ts.push_back(t2);
        }
    }
    sort(ts.begin(), ts.end());

    double area = 0;
    for (size_t i = 0; i < ts.size() - 1; i++) {
        double t1 = ts[i], t2 = ts[i+1];
        if (t2 - t1 < 1e-12) continue;
        
        Point2D q1 = {p1.x + t1 * dx, p1.y + t1 * dy};
        Point2D q2 = {p1.x + t2 * dx, p1.y + t2 * dy};
        Point2D m = {(q1.x + q2.x) / 2.0, (q1.y + q2.y) / 2.0};
        
        if (m.x * m.x + m.y * m.y <= r * r * (1.0 + 1e-11)) {
            area += 0.5 * (q1.x * q2.y - q1.y * q2.x);
        } else {
            double th1 = atan2(q1.y, q1.x);
            double th2 = atan2(q2.y, q2.x);
            double dth = th2 - th1;
            while (dth > M_PI) dth -= 2 * M_PI;
            while (dth < -M_PI) dth += 2 * M_PI;
            area += 0.5 * r * r * dth;
        }
    }
    return area;
}

double circle_polygon_area(double cx, double cy, double r, const vector<Point2D>& poly) {
    if (poly.size() < 3) return 0.0;
    double area = 0.0;
    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 abs(area);
}

double f(int X, int Y, vector<Circle> C) {
    vector<Circle> unique_C;
    for (const auto& c : C) {
        bool dup = false;
        for (auto& uc : unique_C) {
            if (abs(c.x - uc.x) < 1e-7 && abs(c.y - uc.y) < 1e-7) {
                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.0;

    double area_sum = 0.0;

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

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

            double a = 2.0 * (C[i].x - C[j].x);
            double b = 2.0 * (C[i].y - C[j].y);
            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);

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

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

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

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