結果
| 問題 | No.3675 偏光板 |
| コンテスト | |
| ユーザー |
👑  みうね
|
| 提出日時 | 2026-08-21 17:12:52 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 15,116 bytes |
| 記録 | |
| コンパイル時間 | 1,677 ms |
| コンパイル使用メモリ | 214,484 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-09-04 22:31:01 |
| 合計ジャッジ時間 | 20,540 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 51 TLE * 2 -- * 1 |
ソースコード
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <tuple>
#include <vector>
using i64 = long long;
using i128 = __int128_t;
#ifdef POLARIZED_WINDOW_REAL_TYPE
using Real = POLARIZED_WINDOW_REAL_TYPE;
#else
using Real = long double;
#endif
inline Real geo_sqrt(Real x) { using std::sqrt; return sqrt(x); }
inline Real geo_acos(Real x) { using std::acos; return acos(x); }
inline Real geo_atan2(Real y, Real x) { using std::atan2; return atan2(y, x); }
inline Real geo_cos(Real x) { using std::cos; return cos(x); }
inline Real geo_sin(Real x) { using std::sin; return sin(x); }
struct Point {
Real x, y;
};
struct Circle {
i64 x, y, r;
friend bool operator<(const Circle& a, const Circle& b) {
return std::tie(a.x, a.y, a.r) < std::tie(b.x, b.y, b.r);
}
friend bool operator==(const Circle& a, const Circle& b) {
return a.x == b.x && a.y == b.y && a.r == b.r;
}
};
inline Real cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
// Area of [0,X] x [0,Y] intersected with the union of the disks.
inline Real clipped_circle_union_area(std::vector<Circle> circles, i64 X, i64 Y) {
std::sort(circles.begin(), circles.end());
circles.erase(std::unique(circles.begin(), circles.end()), circles.end());
const Real PI = geo_acos(Real(-1)), TAU = 2 * PI;
Real twice_area = 0;
for (int i = 0; i < (int)circles.size(); ++i) {
const Circle& c = circles[i];
std::vector<std::pair<Real, Real>> hidden;
bool all_hidden = false;
// Add the cyclic interval center-half <= theta <= center+half.
auto add_cyclic = [&](Real center, Real half) {
if (half <= 0) return;
if (half >= PI) { all_hidden = true; return; }
Real l = center - half, r = center + half;
while (l < 0) l += TAU, r += TAU;
while (l >= TAU) l -= TAU, r -= TAU;
if (r <= TAU) hidden.push_back({l, r});
else {
hidden.push_back({l, TAU});
hidden.push_back({0, r - TAU});
}
};
// Add angles satisfying cos(theta-center) > k. Endpoints have zero area.
auto add_halfplane = [&](Real center, Real k) {
if (k <= -1) all_hidden = true;
else if (k < 1) add_cyclic(center, geo_acos(std::clamp(k, Real(-1), Real(1))));
};
// Portions outside the four sides of the window.
add_halfplane(PI, (Real)c.x / c.r); // x < 0
add_halfplane(0, ((Real)X - c.x) / c.r); // x > X
add_halfplane(1.5L * PI, (Real)c.y / c.r); // y < 0
add_halfplane(0.5L * PI, ((Real)Y - c.y) / c.r);// y > Y
for (int j = 0; j < (int)circles.size() && !all_hidden; ++j) if (i != j) {
const Circle& d = circles[j];
i128 dx = (i128)d.x - c.x, dy = (i128)d.y - c.y;
i128 dist2 = dx * dx + dy * dy;
i64 sum = c.r + d.r;
if (dist2 >= (i128)sum * sum) continue; // disjoint or externally tangent
if (d.r >= c.r) {
i64 dif = d.r - c.r;
if (dist2 <= (i128)dif * dif) { all_hidden = true; break; }
}
if (c.r > d.r) {
i64 dif = c.r - d.r;
if (dist2 <= (i128)dif * dif) continue; // d lies inside c
}
Real dist = geo_sqrt((Real)dist2);
Real phi = geo_atan2((Real)(d.y - c.y), (Real)(d.x - c.x));
Real z = (dist * dist + (Real)c.r * c.r - (Real)d.r * d.r)
/ (2 * dist * c.r);
add_cyclic(phi, geo_acos(std::clamp(z, Real(-1), Real(1))));
}
if (all_hidden) continue;
std::sort(hidden.begin(), hidden.end());
std::vector<std::pair<Real, Real>> merged;
for (auto seg : hidden) {
if (seg.second <= seg.first) continue;
if (merged.empty() || seg.first > merged.back().second)
merged.push_back(seg);
else
merged.back().second = std::max(merged.back().second, seg.second);
}
// The complement consists exactly of exposed CCW arcs. For an arc
// alpha..beta, integral(x dy-y dx) is cross(o,p(beta)-p(alpha))+r^2*dtheta.
Real at = 0;
auto add_arc = [&](Real a, Real b) {
if (b <= a) return;
Point delta{(Real)c.r * (geo_cos(b) - geo_cos(a)),
(Real)c.r * (geo_sin(b) - geo_sin(a))};
twice_area += cross(Point{(Real)c.x, (Real)c.y}, delta)
+ (Real)c.r * c.r * (b - a);
};
for (auto [l, r] : merged) { add_arc(at, l); at = std::max(at, r); }
add_arc(at, TAU);
}
// Covered portions of the rectangle boundary, traversed counterclockwise.
std::array<Point, 4> vertex{{{0, 0}, {(Real)X, 0}, {(Real)X, (Real)Y}, {0, (Real)Y}}};
for (int side = 0; side < 4; ++side) {
Point a = vertex[side], b = vertex[(side + 1) % 4];
Point v{b.x - a.x, b.y - a.y};
Real len2 = v.x * v.x + v.y * v.y;
std::vector<std::pair<Real, Real>> intervals;
for (const Circle& c : circles) {
Real wx = (Real)c.x - a.x, wy = (Real)c.y - a.y;
Real t0 = (wx * v.x + wy * v.y) / len2;
Real px = a.x + t0 * v.x - c.x, py = a.y + t0 * v.y - c.y;
Real rem = (Real)c.r * c.r - px * px - py * py;
if (rem < 0) continue;
Real dt = geo_sqrt(std::max((Real)0, rem) / len2);
Real l = std::max((Real)0, Real(t0 - dt));
Real r = std::min((Real)1, Real(t0 + dt));
if (l < r) intervals.push_back({l, r});
}
std::sort(intervals.begin(), intervals.end());
Real last_l = 0, last_r = 0;
bool have = false;
auto add_segment = [&](Real l, Real r) {
Point p{a.x + l * v.x, a.y + l * v.y};
Point q{a.x + r * v.x, a.y + r * v.y};
twice_area += cross(p, q);
};
for (auto [l, r] : intervals) {
if (!have) last_l = l, last_r = r, have = true;
else if (l > last_r) add_segment(last_l, last_r), last_l = l, last_r = r;
else last_r = std::max(last_r, r);
}
if (have) add_segment(last_l, last_r);
}
Real area = twice_area / 2;
Real window = (Real)X * Y;
// Only remove final round-off excursions; geometric classification is not EPS-based.
if (area < 0 && area > -1e-7L) area = 0;
if (area > window && area < window + 1e-7L) area = window;
return area;
}
// Correct but intentionally slow solution.
//
// For every circle, collect all angles at which its boundary crosses another
// circle or the window boundary. Whether an arc is exposed is constant
// between two consecutive angles, so test one midpoint against every circle.
// This takes O(K^3) time for a direction containing K circles.
namespace {
Real normalize_angle(Real angle, Real tau) {
while (angle < 0) angle += tau;
while (angle >= tau) angle -= tau;
return angle;
}
void add_angle(std::vector<Real>& angles, Real angle, Real tau) {
angles.push_back(normalize_angle(angle, tau));
}
bool is_exposed(const Point& point, int self,
const std::vector<Circle>& circles, i64 X, i64 Y) {
if (point.x <= 0 || point.x >= (Real)X ||
point.y <= 0 || point.y >= (Real)Y) {
return false;
}
for (int j = 0; j < (int)circles.size(); ++j) {
if (j == self) continue;
Real dx = point.x - circles[j].x;
Real dy = point.y - circles[j].y;
if (dx * dx + dy * dy < (Real)circles[j].r * circles[j].r) {
return false;
}
}
return true;
}
bool is_covered(const Point& point, const std::vector<Circle>& circles) {
for (const Circle& circle : circles) {
Real dx = point.x - circle.x;
Real dy = point.y - circle.y;
if (dx * dx + dy * dy < (Real)circle.r * circle.r) return true;
}
return false;
}
Real clipped_circle_union_area_slow(std::vector<Circle> circles, i64 X, i64 Y) {
std::sort(circles.begin(), circles.end());
circles.erase(std::unique(circles.begin(), circles.end()), circles.end());
const Real PI = geo_acos(Real(-1));
const Real TAU = 2 * PI;
Real twice_area = 0;
for (int i = 0; i < (int)circles.size(); ++i) {
const Circle& circle = circles[i];
std::vector<Real> angles{0, TAU};
for (int j = 0; j < (int)circles.size(); ++j) {
if (i == j) continue;
const Circle& other = circles[j];
i128 integer_dx = (i128)other.x - circle.x;
i128 integer_dy = (i128)other.y - circle.y;
i128 distance_squared = integer_dx * integer_dx
+ integer_dy * integer_dy;
i64 radius_difference = std::abs(circle.r - other.r);
i64 radius_sum = circle.r + other.r;
if (distance_squared == 0 ||
distance_squared < (i128)radius_difference * radius_difference ||
distance_squared > (i128)radius_sum * radius_sum) {
continue;
}
Real dx = (Real)integer_dx;
Real dy = (Real)integer_dy;
Real distance = geo_sqrt((Real)distance_squared);
Real base = geo_atan2(dy, dx);
Real cosine = (distance * distance + (Real)circle.r * circle.r
- (Real)other.r * other.r)
/ (2 * distance * circle.r);
Real delta = geo_acos(std::clamp(cosine, Real(-1), Real(1)));
add_angle(angles, base - delta, TAU);
add_angle(angles, base + delta, TAU);
}
auto add_vertical_crossings = [&](Real x) {
Real cosine = (x - circle.x) / circle.r;
if (cosine < Real(-1) || cosine > Real(1)) return;
Real angle = geo_acos(std::clamp(cosine, Real(-1), Real(1)));
add_angle(angles, angle, TAU);
add_angle(angles, -angle, TAU);
};
auto add_horizontal_crossings = [&](Real y) {
Real sine = (y - circle.y) / circle.r;
if (sine < Real(-1) || sine > Real(1)) return;
Real delta = geo_acos(std::clamp(sine, Real(-1), Real(1)));
add_angle(angles, PI / 2 - delta, TAU);
add_angle(angles, PI / 2 + delta, TAU);
};
add_vertical_crossings(0);
add_vertical_crossings(X);
add_horizontal_crossings(0);
add_horizontal_crossings(Y);
std::sort(angles.begin(), angles.end());
for (int k = 0; k + 1 < (int)angles.size(); ++k) {
Real left = angles[k];
Real right = angles[k + 1];
if (right <= left) continue;
Real middle = (left + right) / 2;
Point sample{(Real)circle.x + circle.r * geo_cos(middle),
(Real)circle.y + circle.r * geo_sin(middle)};
if (!is_exposed(sample, i, circles, X, Y)) continue;
Point delta{(Real)circle.r * (geo_cos(right) - geo_cos(left)),
(Real)circle.r * (geo_sin(right) - geo_sin(left))};
twice_area += cross(Point{(Real)circle.x, (Real)circle.y}, delta)
+ (Real)circle.r * circle.r * (right - left);
}
}
// Add covered portions of the rectangle boundary in counterclockwise order.
const std::vector<Point> vertices{{0, 0}, {(Real)X, 0},
{(Real)X, (Real)Y}, {0, (Real)Y}};
for (int side = 0; side < 4; ++side) {
Point from = vertices[side];
Point to = vertices[(side + 1) % 4];
Point direction{to.x - from.x, to.y - from.y};
Real length_squared = direction.x * direction.x
+ direction.y * direction.y;
std::vector<Real> positions{0, 1};
for (const Circle& circle : circles) {
Real wx = (Real)circle.x - from.x;
Real wy = (Real)circle.y - from.y;
Real center = (wx * direction.x + wy * direction.y) / length_squared;
Real px = from.x + center * direction.x - circle.x;
Real py = from.y + center * direction.y - circle.y;
Real remaining = (Real)circle.r * circle.r - px * px - py * py;
if (remaining <= 0) continue;
Real offset = geo_sqrt(remaining / length_squared);
Real left = center - offset;
Real right = center + offset;
if (0 < left && left < 1) positions.push_back(left);
if (0 < right && right < 1) positions.push_back(right);
}
std::sort(positions.begin(), positions.end());
bool have_covered_run = false;
Real covered_left = 0;
Real covered_right = 0;
auto flush_covered_run = [&] {
if (!have_covered_run) return;
Point p{from.x + covered_left * direction.x,
from.y + covered_left * direction.y};
Point q{from.x + covered_right * direction.x,
from.y + covered_right * direction.y};
twice_area += cross(p, q);
have_covered_run = false;
};
for (int k = 0; k + 1 < (int)positions.size(); ++k) {
Real left = positions[k];
Real right = positions[k + 1];
if (right <= left) continue;
Real middle = (left + right) / 2;
Point sample{from.x + middle * direction.x,
from.y + middle * direction.y};
if (is_covered(sample, circles)) {
if (!have_covered_run) {
covered_left = left;
have_covered_run = true;
}
covered_right = right;
} else {
flush_covered_run();
}
}
flush_covered_run();
}
Real area = twice_area / 2;
Real window = (Real)X * Y;
if (area < 0 && area > -1e-7L) area = 0;
if (area > window && area < window + 1e-7L) area = window;
return area;
}
} // namespace
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 X, Y;
int N;
if (!(std::cin >> X >> Y >> N)) return 0;
std::vector<Circle> vertical, horizontal;
for (int i = 0; i < N; ++i) {
Circle circle;
char direction;
std::cin >> circle.x >> circle.y >> circle.r >> direction;
(direction == 'V' ? vertical : horizontal).push_back(circle);
}
Real vertical_area = clipped_circle_union_area_slow(vertical, X, Y);
Real horizontal_area = clipped_circle_union_area_slow(horizontal, X, Y);
Real window = (Real)X * Y;
Real answer = window - (vertical_area + horizontal_area) / 2;
if (answer < 0 && answer > -1e-7L) answer = 0;
if (answer > window && answer < window + 1e-7L) answer = window;
std::cout << std::fixed << std::setprecision(15) << answer << '\n';
}