QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94706#3233. Everything Has Changedwhatever#100 ✓9ms3884kbC++171.2kb2023-04-07 15:47:292023-04-07 15:47:32

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 15:47:32]
  • Judged
  • Verdict: 100
  • Time: 9ms
  • Memory: 3884kb
  • [2023-04-07 15:47:29]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using namespace std;
using i64 = long long;
using i128 = __int128_t;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rng(int l, int r) { return l + rnd() % (r - l + 1); }

const double pi = acos(-1.0);
double get_ang(double a, double b, double c) {
    return acos((a * a + b * b - c * c) / (2 * a * b));
}

void solve() {
    int n, R;
    cin >> n >> R;
    double ans = 2 * pi * R;
    rep(i, 1, n) {
        int x, y, r;
        cin >> x >> y >> r;
        int D = x * x + y * y;
        if (D < R * R && r < R && D < (R - r) * (R - r)) continue;
        if (D > R * R && D >= (R + r) * (R + r)) continue;
        double d = sqrt(D);
        ans += get_ang(r, d, R) * 2 * r;
        ans -= get_ang(R, d, r) * 2 * R;
    }
    cout << setprecision(20) << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

    int T; cin >> T;
    while (T--) solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 3884kb

input:

1000
55 551
85 920 149
443 -899 185
20 597 32
900 59 191
-545 424 7
-878 -69 63
-143 -844 282
-390 961 275
839 -549 227
-582 -147 27
-439 550 99
-70 706 69
224 -937 20
-968 609 125
141 700 5
527 -290 15
-171 640 4
-613 -301 65
679 -175 14
314 -486 3
-287 528 17
-553 -108 3
-202 521 2
573 -301 24
905...

output:

5793.0285377859481741
730.89560459962319783
106.81415022205297305
5607.3394168535141944
4817.0445137481583515
7132.2657518376390726
97.323741217409548199
2579.5598791611910201
2831.6319844540098529
4828.8504561752170048
2690.1493897757677587
8643.5476551755582477
5747.5882245565790072
2696.436640535...

result:

ok 1000 numbers