結果
| 問題 | No.3675 偏光板 |
| コンテスト | |
| ユーザー |
👑  みうね
|
| 提出日時 | 2026-08-21 13:08:29 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 278 ms / 2,000 ms |
| + 38µs | |
| コード長 | 7,222 bytes |
| 記録 | |
| コンパイル時間 | 3,164 ms |
| コンパイル使用メモリ | 362,904 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-09-04 22:29:29 |
| 合計ジャッジ時間 | 7,612 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 54 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Circle {
ll x, y, r;
auto operator<=>(const Circle &) const = default;
};
double solve(ll X, ll Y, vector<Circle> &circles) {
vector<pair<double, double>> topedge, rightedge;
double ret = 0;
for (int i = 0; i < (int)circles.size(); ++i) {
auto &c = circles[i];
if (c.x + c.r <= 0 || X <= c.x - c.r || c.y + c.r <= 0 || Y <= c.y - c.r) {
continue;
}
{
bool hidden = false;
for (int j = 0; j < (int)circles.size(); ++j) {
if (i == j) continue;
auto &cc = circles[j];
if (c.r >= cc.r) continue;
if ((c.x - cc.x) * (c.x - cc.x) + (c.y - cc.y) * (c.y - cc.y) <= (cc.r - c.r) * (cc.r - c.r)) {
hidden = true;
break;
}
}
if (hidden) continue;
}
if (c.y + c.r > Y) {
ll dy = abs(Y - c.y);
double dx = sqrt(double(c.r * c.r - dy * dy));
double l = c.x - dx, r = c.x + dx;
if (0 < r && l < X) {
l = clamp(l, double(0), double(X));
r = clamp(r, double(0), double(X));
topedge.emplace_back(l, r);
}
}
if (c.x + c.r > X) {
ll dx = abs(X - c.x);
double dy = sqrt(double(c.r * c.r - dx * dx));
double l = c.y - dy, r = c.y + dy;
if (0 < r && l < Y) {
l = clamp(l, double(0), double(Y));
r = clamp(r, double(0), double(Y));
rightedge.emplace_back(l, r);
}
}
vector<pair<double, double>> circum;
for (int j = 0; j < (int)circles.size(); ++j) {
if (i == j) continue;
auto &cc = circles[j];
if ((c.x - cc.x) * (c.x - cc.x) + (c.y - cc.y) * (c.y - cc.y) <= (cc.r - c.r) * (cc.r - c.r)) continue;
if ((c.x - cc.x) * (c.x - cc.x) + (c.y - cc.y) * (c.y - cc.y) >= (cc.r + c.r) * (cc.r + c.r)) continue;
double d = sqrt(double((c.x - cc.x) * (c.x - cc.x) + (c.y - cc.y) * (c.y - cc.y)));
double phi = atan2(double(cc.y - c.y), double(cc.x - c.x));
double delta = acos(clamp(double(d * d + c.r * c.r - cc.r * cc.r) / (double(2) * d * c.r), -1.0, 1.0));
double l = phi - delta, r = phi + delta;
if (l < -M_PI) {
circum.emplace_back(l + M_PI * 2, M_PI);
circum.emplace_back(-M_PI, r);
} else if (r > M_PI) {
circum.emplace_back(l, M_PI);
circum.emplace_back(-M_PI, r - M_PI * 2);
} else {
circum.emplace_back(l, r);
}
}
if (c.x - c.r < 0) {
double theta = acos(clamp(double(c.x) / double(c.r), -1.0, 1.0));
circum.emplace_back(M_PI - theta, M_PI);
circum.emplace_back(-M_PI, -M_PI + theta);
}
if (c.x + c.r > X) {
double theta = acos(clamp(double(X - c.x) / double(c.r), -1.0, 1.0));
circum.emplace_back(-theta, theta);
}
if (c.y - c.r < 0) {
double theta = acos(clamp(double(c.y) / double(c.r), -1.0, 1.0));
double l = -M_PI_2 - theta, r = -M_PI_2 + theta;
if (l < -M_PI) {
circum.emplace_back(l + M_PI * 2, M_PI);
circum.emplace_back(-M_PI, r);
} else if (r > M_PI) {
circum.emplace_back(l, M_PI);
circum.emplace_back(-M_PI, r - M_PI * 2);
} else {
circum.emplace_back(l, r);
}
}
if (c.y + c.r > Y) {
double theta = acos(clamp(double(Y - c.y) / double(c.r), -1.0, 1.0));
double l = M_PI_2 - theta, r = M_PI_2 + theta;
if (l < -M_PI) {
circum.emplace_back(l + M_PI * 2, M_PI);
circum.emplace_back(-M_PI, r);
} else if (r > M_PI) {
circum.emplace_back(l, M_PI);
circum.emplace_back(-M_PI, r - M_PI * 2);
} else {
circum.emplace_back(l, r);
}
}
circum.emplace_back(-numeric_limits<double>::infinity(), -M_PI);
circum.emplace_back(M_PI, numeric_limits<double>::infinity());
{
sort(circum.begin(), circum.end());
circum.erase(unique(circum.begin(), circum.end()), circum.end());
vector<pair<double, double>> merged;
for (auto &p : circum) {
if (merged.empty() || merged.back().second < p.first) {
merged.emplace_back(p);
} else {
if (merged.back().second < p.second) {
merged.back().second = p.second;
}
}
}
circum = move(merged);
}
if (circum.size() == 1) continue;
double s = 0;
for (int j = 0; j < int(circum.size()) - 1; ++j) {
double a = circum[j].second, b = circum[j + 1].first;
s += (c.r * c.x * (sin(b) - sin(a)) - c.r * c.y * (cos(b) - cos(a)) + c.r * c.r * (b - a)) / 2;
}
ret += s;
}
{
sort(topedge.begin(), topedge.end());
topedge.erase(unique(topedge.begin(), topedge.end()), topedge.end());
vector<pair<double, double>> merged;
for (auto &p : topedge) {
if (merged.empty() || merged.back().second < p.first) {
merged.emplace_back(p);
} else {
if (merged.back().second < p.second) {
merged.back().second = p.second;
}
}
}
topedge = move(merged);
}
for (auto &p : topedge) {
double s = Y * (p.second - p.first) / 2;
ret += s;
}
{
sort(rightedge.begin(), rightedge.end());
rightedge.erase(unique(rightedge.begin(), rightedge.end()), rightedge.end());
vector<pair<double, double>> merged;
for (auto &p : rightedge) {
if (merged.empty() || merged.back().second < p.first) {
merged.emplace_back(p);
} else {
if (merged.back().second < p.second) {
merged.back().second = p.second;
}
}
}
rightedge = move(merged);
}
for (auto &p : rightedge) {
double s = X * (p.second - p.first) / 2;
ret += s;
}
return ret;
}
int main() {
ll X, Y, N;
cin >> X >> Y >> N;
vector<vector<Circle>> c(2);
for (int i = 0; i < N; ++i) {
int x, y, r;
char d;
cin >> x >> y >> r >> d;
if (d == 'V') {
c[0].push_back({x, y, r});
} else {
c[1].push_back({x, y, r});
}
}
for (int k = 0; k < 2; ++k) {
sort(c[k].begin(), c[k].end());
c[k].erase(unique(c[k].begin(), c[k].end()), c[k].end());
}
double ans = double(X * Y) - (solve(X, Y, c[0]) + solve(X, Y, c[1])) / double(2);
cout << fixed << setprecision(20) << ans << endl;
}