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

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

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

ソースコード

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

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;

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

        if (d1 >= -1e-11) {
            res.push_back(p1);
            if (d2 < -1e-11) {
                double t = d1 / (d1 - d2);
                t = max(0.0, min(1.0, t));
                res.push_back({p1.x + t * (p2.x - p1.x), p1.y + t * (p2.y - p1.y)});
            }
        } else if (d2 >= -1e-11) {
            double t = d1 / (d1 - d2);
            t = max(0.0, min(1.0, t));
            res.push_back({p1.x + t * (p2.x - p1.x), p1.y + t * (p2.y - p1.y)});
        }
    }
    return res;
}
double circle_polygon_area(double cx, double cy, double R, const vector<Point2D>& poly) {
    int n = poly.size();
    if (n < 3) return 0.0;
    double area = 0.0;
    double R2 = R * R;
    for (int i = 0; i < n; i++) {
        Point2D p1 = poly[i];
        Point2D p2 = poly[(i + 1) % n];
        double x1 = p1.x - cx, y1 = p1.y - cy;
        double x2 = p2.x - cx, y2 = p2.y - cy;
        double dx = x2 - x1, dy = y2 - y1;
        double a = dx * dx + dy * dy;
        double b = 2.0 * (x1 * dx + y1 * dy);
        double c = x1 * x1 + y1 * y1 - R2;
        vector<double> ts = {0.0, 1.0};
        if (abs(a) > 1e-12) {
            double disc = b * b - 4 * a * c;
            if (disc > 0) {
                double sq = sqrt(disc);
                double t1 = (-b - sq) / (2 * a);
                double t2 = (-b + sq) / (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());
        for (size_t j = 0; j < ts.size() - 1; j++) {
            double ta = ts[j], tb = ts[j + 1];
            if (tb - ta < 1e-12) continue;
            Point2D sub_p1 = {x1 + ta * dx, y1 + ta * dy};
            Point2D sub_p2 = {x1 + tb * dx, y1 + tb * dy};
            double mx = (sub_p1.x + sub_p2.x) / 2.0;
            double my = (sub_p1.y + sub_p2.y) / 2.0;
            
            if (mx * mx + my * my < R2 - 1e-9) {
                area += 0.5 * (sub_p1.x * sub_p2.y - sub_p1.y * sub_p2.x);
            } else {
                double ang1 = atan2(sub_p1.y, sub_p1.x);
                double ang2 = atan2(sub_p2.y, sub_p2.x);
                double dtheta = atan2(sin(ang2 - ang1), cos(ang2 - ang1));
                area += 0.5 * R2 * dtheta;
            }
        }
    }
    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;
}