Challenge: Painting Figures
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464915986
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/painting-figures/problem
Cerinta
Carl is an abstract artist painting $n$ figures. Each figure $i$ is described as a segment on a plane with ends in $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ having radius $r$; this means every point with a distance $\le r$ from the segment is part of figure $i$. Carl wants to make sure he has enough paint for all the figures, so he wants to know the *total area* they will cover.
Given the locations for all the figures, find and print a real number denoting the total area covered by all $n$ figures with an absolute or relative error of *at most* $10^{-6}$.Input Format
The first line contains single integer, $n$, denoting the number of figures.
Each line $i$ of the $n$ subsequent lines contains five space-separated integers describing the respective values of $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, and $r$ for figure $i$.Output Format
Print a real number denoting the total area covered by all $n$ figures with an absolute or relative error of *at most* $10^{-6}$.Constraints
+ $1 \le n \le 200$
- $0 \le |x_{1}|, |y_{1}|, |x_{2}|, |y_{2}|, r \le 10^3$.
- It's guaranteed that each segment's length and $r$ values are positive.Cod sursa
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
struct Fig {
double x1, y1, x2, y2;
double dx, dy;
double r, r2;
double len2, len, rlen;
};
struct Node {
double a, b;
double fa, fb, fm;
double whole;
double eps;
int depth;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
if (n <= 0) {
cout << fixed << setprecision(10) << 0.0 << '\n';
return 0;
}
vector<Fig> figs;
figs.reserve(n);
vector<double> cuts;
cuts.reserve(4 * n + 4);
double y_lo = 1e100, y_hi = -1e100;
for (int i = 0; i < n; ++i) {
Fig f{};
cin >> f.x1 >> f.y1 >> f.x2 >> f.y2 >> f.r;
f.dx = f.x2 - f.x1;
f.dy = f.y2 - f.y1;
f.r2 = f.r * f.r;
f.len2 = f.dx * f.dx + f.dy * f.dy;
f.len = sqrt(f.len2);
f.rlen = f.r * f.len;
figs.push_back(f);
double lo = min(f.y1, f.y2) - f.r;
double hi = max(f.y1, f.y2) + f.r;
y_lo = min(y_lo, lo);
y_hi = max(y_hi, hi);
cuts.push_back(f.y1 - f.r);
cuts.push_back(f.y1 + f.r);
cuts.push_back(f.y2 - f.r);
cuts.push_back(f.y2 + f.r);
}
const double EPS = 1e-12;
auto union_length_at = [&](double y) -> double {
pair<double, double> ivs[205];
int iv_cnt = 0;
for (const auto& f : figs) {
double xl = 1e100, xr = -1e100;
// Endpoint circles
double d = y - f.y1;
double d2 = d * d;
if (d2 <= f.r2 + EPS) {
double hw = sqrt(max(0.0, f.r2 - d2));
xl = min(xl, f.x1 - hw);
xr = max(xr, f.x1 + hw);
}
d = y - f.y2;
d2 = d * d;
if (d2 <= f.r2 + EPS) {
double hw = sqrt(max(0.0, f.r2 - d2));
xl = min(xl, f.x2 - hw);
xr = max(xr, f.x2 + hw);
}
// Segment body: intersection of strip around infinite line and projection slab.
bool has = true;
double lo = -1e100, hi = 1e100;
if (fabs(f.dy) > EPS) {
// |dy*x + (dx*y1 - dy*x1 - dx*y)| <= r*|D|
double c0 = f.dx * f.y1 - f.dy * f.x1 - f.dx * y;
lo = (-f.rlen - c0) / f.dy;
hi = ( f.rlen - c0) / f.dy;
if (lo > hi) swap(lo, hi);
} else {
// Horizontal segment: strip active only if |y-y1|<=r.
if (fabs(y - f.y1) > f.r + EPS) {
has = false;
}
}
if (has) {
if (fabs(f.dx) > EPS) {
// 0 <= dx*x + (-dx*x1 + dy*(y-y1)) <= |D|^2
double p0 = -f.dx * f.x1 + f.dy * (y - f.y1);
double a = (-p0) / f.dx;
double b = (f.len2 - p0) / f.dx;
if (a > b) swap(a, b);
if (a > lo) lo = a;
if (b < hi) hi = b;
} else {
// Vertical segment: projection independent of x.
double P = f.dy * (y - f.y1);
if (P < -EPS || P > f.len2 + EPS) has = false;
}
}
if (has && lo <= hi + EPS) {
if (lo < xl) xl = lo;
if (hi > xr) xr = hi;
}
if (xl <= xr + EPS) ivs[iv_cnt++] = {xl, xr};
}
if (iv_cnt == 0) return 0.0;
sort(ivs, ivs + iv_cnt);
double total = 0.0;
double ca = ivs[0].first, cb = ivs[0].second;
for (int i = 1; i < iv_cnt; ++i) {
double a = ivs[i].first, b = ivs[i].second;
if (a <= cb + EPS) {
if (b > cb) cb = b;
} else {
total += cb - ca;
ca = a;
cb = b;
}
}
total += cb - ca;
return total;
};
auto integrate_adaptive = [&](double a, double b, double tol) -> double {
double fa = union_length_at(a);
double fb = union_length_at(b);
double m = (a + b) * 0.5;
double fm = union_length_at(m);
double whole = (b - a) / 6.0 * (fa + 4.0 * fm + fb);
vector<Node> st;
st.reserve(1 << 15);
st.push_back({a, b, fa, fb, fm, whole, tol, 0});
double result = 0.0;
while (!st.empty()) {
Node cur = st.back();
st.pop_back();
double l = cur.a, r = cur.b;
double mid = (l + r) * 0.5;
double m1 = (l + mid) * 0.5;
double m2 = (mid + r) * 0.5;
double fm1 = union_length_at(m1);
double fm2 = union_length_at(m2);
double h = r - l;
double left = h / 12.0 * (cur.fa + 4.0 * fm1 + cur.fm);
double right = h / 12.0 * (cur.fm + 4.0 * fm2 + cur.fb);
double total = left + right;
double diff = total - cur.whole;
if (cur.depth >= 50 || (cur.depth >= 8 && fabs(diff) <= 15.0 * cur.eps)) {
result += total + diff / 15.0;
} else {
double he = cur.eps * 0.5;
st.push_back({mid, r, cur.fm, cur.fb, fm2, right, he, cur.depth + 1});
st.push_back({l, mid, cur.fa, cur.fm, fm1, left, he, cur.depth + 1});
}
}
return result;
};
cuts.push_back(y_lo);
cuts.push_back(y_hi);
sort(cuts.begin(), cuts.end());
vector<double> uniq;
uniq.reserve(cuts.size());
for (double v : cuts) {
if (uniq.empty() || fabs(v - uniq.back()) > 1e-12) uniq.push_back(v);
}
// Dynamic global tolerance from coarse area estimate.
double area_est = 0.0;
{
const int M_EST = 96;
double L = y_hi - y_lo;
if (L > 0.0) {
double h = L / M_EST;
double prev = union_length_at(y_lo);
for (int i = 1; i <= M_EST; ++i) {
double y = y_lo + h * i;
double cur = union_length_at(y);
area_est += (prev + cur) * 0.5 * h;
prev = cur;
}
}
}
struct Seg { double a, b, eps; };
vector<Seg> segs;
segs.reserve(uniq.size());
const double total_tol = 2e-8 * max(1.0, fabs(area_est));
const double total_len = max(1e-12, y_hi - y_lo);
for (size_t i = 1; i < uniq.size(); ++i) {
double a = uniq[i - 1], b = uniq[i];
if (b - a <= 1e-12) continue;
double seg_tol = total_tol * (b - a) / total_len;
if (seg_tol < 1e-12) seg_tol = 1e-12;
segs.push_back({a, b, seg_tol});
}
double ans = 0.0;
unsigned hc = thread::hardware_concurrency();
int tcnt = (hc == 0 ? 1 : (int)hc);
if (tcnt > 4) tcnt = 4;
if (tcnt <= 1 || segs.size() < 24) {
for (const auto& s : segs) ans += integrate_adaptive(s.a, s.b, s.eps);
} else {
vector<double> partial(tcnt, 0.0);
vector<thread> th;
th.reserve(tcnt);
for (int t = 0; t < tcnt; ++t) {
th.emplace_back([&, t]() {
double loc = 0.0;
for (size_t j = (size_t)t; j < segs.size(); j += (size_t)tcnt) {
const auto& s = segs[j];
loc += integrate_adaptive(s.a, s.b, s.eps);
}
partial[t] = loc;
});
}
for (auto& thd : th) thd.join();
for (double v : partial) ans += v;
}
cout << fixed << setprecision(10) << ans << '\n';
return 0;
}
HackerRank Geometry – Painting Figures