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

• 問題: No.3675 偏光板
• ユーザー: TKTYI
• 提出日時: 2026-09-02 23:57:03
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 341 ms / 2,000 ms
• コード長: 3,581 bytes
• コンパイル時間: 2,745 ms
• コンパイル使用メモリ: 369,824 KB
• 実行使用メモリ: 9,796 KB
• 最終ジャッジ日時: 2026-09-04 23:10:44
• 合計ジャッジ時間: 6,815 ms
• ジャッジサーバーID （参考情報）: judge4_1 / judge2_0

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

ソースコード

#include<bits/stdc++.h>
using namespace std;
const double PI = 3.141592653589793238;
double f(int X, int Y, vector<int> _x, vector<int> _y, vector<int> _r) {
  vector<int> x, y, r;

  int N = _x.size();
  vector<int> I(N);
  iota(I.begin(), I.end(), 0);
  sort(I.begin(), I.end(), [&](int i, int j) {return _r[i] > _r[j];});
  for (int i : I) {
    bool ok = 1;
    for (int j : I) {
      if (i == j) break;
      long long d = 1ll * (_x[i] - _x[j]) * (_x[i] - _x[j]) + 1ll * (_y[i] - _y[j]) * (_y[i] - _y[j]);
      if (d <= 1ll * (_r[i] - _r[j]) * (_r[i] - _r[j])) {
        ok = 0;
        break;
      }
    }
    if (ok) {
      x.emplace_back(_x[i]);
      y.emplace_back(_y[i]);
      r.emplace_back(_r[i]);
    }
  }
  N = x.size();
  double ans = 0;

  vector<pair<double, double>> upper;
  for (int i = 0; i < N; i++) {
    if (abs(Y - y[i]) < r[i]) {
      double d = sqrt(1ll * r[i] * r[i] - 1ll * (Y - y[i]) * (Y - y[i]));
      upper.emplace_back(x[i] - d, x[i] + d);
    }
  }
  sort(upper.begin(), upper.end());
  for (int i = 0; i < upper.size(); i++) {
    auto [L, R] = upper[i];
    while (i < upper.size() && upper[i].first < R) R = max(R, upper[i++].second);
    L = max(L, double(0));
    R = min(R, double(X));
    ans += max(R - L, double(0)) * Y;
    i--;
  }

  for (int i = 0; i < N; i++) {
    if (x[i] + r[i] <= 0 || y[i] + r[i] <= 0 || x[i] - r[i] >= X || y[i] - r[i] >= Y) continue;
    vector<pair<double, double>>arg;
    if (abs(y[i] - 0) < r[i]) {
      double t = asin(double(-y[i]) / r[i]);
      arg.emplace_back(PI - t, t);
    }
    if (abs(y[i] - Y) < r[i]) {
      double t = asin(double(Y - y[i]) / r[i]);
      arg.emplace_back(t, PI - t);
    }
    if (abs(x[i] - 0) < r[i]) {
      double t = acos(double(-x[i]) / r[i]);
      arg.emplace_back(t, -t);
    }
    if (abs(x[i] - X) < r[i]) {
      double t = acos(double(X - x[i]) / r[i]);
      arg.emplace_back(-t, t);
    }
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      long long d = 1ll * (x[i] - x[j]) * (x[i] - x[j]) + 1ll * (y[i] - y[j]) * (y[i] - y[j]);
      if (d >= 1ll * (r[i] + r[j]) * (r[i] + r[j])) continue;
      double dt = acos(double(1ll * r[i] * r[i] - 1ll * r[j] * r[j] + d) * 0.5 / sqrt(d) / r[i]);
      double t = atan2(y[j] - y[i], x[j] - x[i]);
      arg.emplace_back(t - dt, t + dt);
    }
    vector<pair<double, double>> _arg;
    for (auto [l, r] : arg) {
      while (l < -PI) l += PI + PI;
      while (l > PI) l -= PI + PI;
      while (r < -PI) r += PI + PI;
      while (r > PI) r -= PI + PI;
      if (l > r) {
        _arg.emplace_back(-PI, r);
        _arg.emplace_back(l, PI);
      }
      else _arg.emplace_back(l, r);
    }
    arg = _arg;
    sort(arg.begin(), arg.end());
    double s = PI * r[i];
    for (int j = 0; j < arg.size(); j++) {
      auto [L, R] = arg[j];
      while (j < arg.size() && arg[j].first <= R) R = max(R, arg[j++].second);
      s += y[i] * (cos(R) - cos(L));
      s -= r[i] * (R - L - (sin(R + R) - sin(L + L)) * 0.5) * 0.5;
      j--;
    }
    ans += r[i] * s;
  }
  return ans;
}
int main() {
  int X, Y, N;
  cin >> X >> Y >> N;
  vector<int> xv, xh, yv, yh, rv, rh;
  while (N--) {
    int x, y, r;
    char d;
    cin >> x >> y >> r >> d;
    if (d == 'V') {
      xv.emplace_back(x);
      yv.emplace_back(y);
      rv.emplace_back(r);
    }
    else {
      xh.emplace_back(x);
      yh.emplace_back(y);
      rh.emplace_back(r);
    }
  }
  double ans = (double) X * Y;
  ans -= f(X, Y, xv, yv, rv) * 0.5;
  ans -= f(X, Y, xh, yh, rh) * 0.5;
  printf("%.20lf\n", ans);
  return 0;
}