Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long double ld;
typedef complex<ld> P;
const ld eps = 1e-8, pi = acos(-1.0);
ld dot (P a, P b) { return real(conj(a) * b); }
ld cross (P a, P b) { return imag(conj(a) * b); }
struct C { P p; ld r, val; };
bool operator<(const C &lhs, const C &rhs) {
return norm(lhs.p) - lhs.r * lhs.r < norm(rhs.p) - rhs.r * rhs.r;
}
struct Range {
ld angle, width;
Range operator*(const Range &rhs) {
ld l1 = angle, w1 = width;
ld l2 = rhs.angle, w2 = rhs.width;
if (l1 > l2) { swap(l1, l2); swap(w1, w2); }
if (l2 - l1 < pi) {
ld d = w1 + l1 - l2;
if (d < eps) return (Range){0, 0};
return (Range){l2, min(w2, d)};
}
else {
ld d = w2 + l2 - l1 - 2*pi;
if (d < eps) return (Range){0, 0};
return (Range){l1, min(w1, d)};
}
}
Range operator+(const Range &rhs) {
if (rhs.width < eps) return *this;
ld l1 = angle, w1 = width;
ld l2 = rhs.angle, w2 = rhs.width;
if (l1 > l2) { swap(l1, l2); swap(w1, w2); }
if (l2 - l1 < pi) return (Range){l1, max(w1, w2 + l2 - l1)};
else return (Range){l2, max(w2, w1 + l1 - l2 + 2*pi)};
}
};
Range circle_range(const C &c1, const C &c2) {
ld w = asin((c1.r + c2.r) / abs(c1.p - c2.p));
ld a = arg(c2.p - c1.p) - w;
if (a < -pi) a += 2 * pi;
return (Range){a, w * 2};
}
int main() {
int N;
cin >> N;
vector<Range> dp(N);
vector<C> circle(N);
REP(i,N) {
ld x, y, r, w;
cin >> x >> y >> r >> w;
circle[i] = (C){P(x, y), r, w};
}
sort(ALL(circle));
REP(i,N) dp[i] = circle_range((C){P(0, 0), 0, 0}, circle[i]);
REP(i,N) REP(j,N) {
if (i == j) continue;
Range range = circle_range(circle[i], circle[j]);
dp[j] = dp[j] + range * dp[i];
}
ld res = 0;
REP(i,N) res += circle[i].val * dp[i].width / 2 / pi;
cout << setprecision(9) << fixed;
cout << res << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment