QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343101#8246. Garden of ThornsElTeeran_ElHayga#AC ✓1ms4352kbC++204.9kb2024-03-01 22:18:392024-03-01 22:18:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-01 22:18:41]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4352kb
  • [2024-03-01 22:18:39]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25;

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

template<class T>
int sgn(T x) { return (x > 0) - (x < 0); }

template<class T>
struct Point {
    typedef Point P;
    T x, y;

    Point(T x = 0, T y = 0) : x(x), y(y) {}

    bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }

    bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }

    P operator+(P p) const { return P(x + p.x, y + p.y); }

    P operator-(P p) const { return P(x - p.x, y - p.y); }

    P operator*(T d) const { return P(x * d, y * d); }

    P operator/(T d) const { return P(x / d, y / d); }

    T dot(P p) const { return x * p.x + y * p.y; }

    T cross(P p) const { return x * p.y - y * p.x; }

    T cross(P a, P b) const { return (a - *this).cross(b - *this); }

    T dist2() const { return x * x + y * y; }

    double dist() const { return sqrt((double) dist2()); }

    double dist(P b) { return (*this - b).dist(); };

    // angle to x-axis in interval [-pi, pi]
    double angle() const { return atan2(y, x); }

    P unit() const { return *this / dist(); } // makes dist()=1
    P perp() const { return P(-y, x); } // rotates +90 degrees
    P normal() const { return perp().unit(); }

    P getVector(const P &p) const { return p - (*this); }

    // returns point rotated 'a' radians ccw around the origin
    P rotate(double a) const {
        return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    friend ostream &operator<<(ostream &os, P p) {
        return os << "(" << p.x << "," << p.y << ")";
    }

    friend istream &operator>>(istream &is, P &p) {
        return is >> p.x >> p.y;
    }


    // Project point onto line through a and b (assuming a != b).
    P projectOnLine(const P &a, const P &b) const {
        P ab = a.getVector(b);
        P ac = a.getVector(*this);
        return a + ab * ac.dot(ab) / a.dist2(b);
    }

    // Project point c onto line segment through a and b (assuming a != b).
    P projectOnSegment(const P &a, const P &b) const {
        P &c = *this;
        P ab = a.getVector(b);
        P ac = a.getVector(c);

        long double r = dot(ac, ab), d = a.dist2(b);
        if (r < 0) return a;
        if (r > d) return b;

        return a + ab * r / d;
    }

    P reflectAroundLine(const P &a, const P &b) const {
        return projectOnLine(a, b) * 2 - (*this);
    }
};

const ld eps = 1e-9;

int dcmp(const ld &a, const ld &b){
    if(fabs(a - b) < eps)
        return 0;

    return (a > b ? 1 : -1);
}

typedef Point<double> P;
#define arg(p, q) atan2(p.cross(q), p.dot(q))
double circlePoly(P c, double r, vector<P> ps) {
    auto tri = [&](P p, P q) {
        auto r2 = r * r / 2;
        P d = q - p;
        auto a = d.dot(p)/d.dist2(), b = (p.dist2()-r*r)/d.dist2();
        auto det = a * a - b;
        if (det <= 0) return arg(p, q) * r2;
        auto s = max(0., -a-sqrt(det)), t = min(1., -a+sqrt(det));
        if (t < 0 || 1 <= s) return arg(p, q) * r2;
        P u = p + d * s, v = p + d * t;
        return arg(p,u) * r2 + u.cross(v)/2 + arg(v,q) * r2;
    };
    auto sum = 0.0;
    for (int i = 0; i < ps.size(); ++i) {
        sum += tri(ps[i] - c, ps[(i + 1) % ps.size()] - c);
    }
    return sum;
}

void solve() {
    int n, r, w, h;
    cin >> n >> r >> w >> h;
    vector<pair<pair<int, int>, int>>vec(n);

    vector<Point<double>>pts = {{0.0, 0.0}, {1.0 * w, 0.0}, {1.0 * w, 1.0 * h}, {0.0, 1.0 * h}};
    double ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> vec[i].first.first >> vec[i].first.second >> vec[i].second;
        ans += circlePoly({1.0 * vec[i].first.first, 1.0 * vec[i].first.second}, r, pts) * vec[i].second;
    }
    ans /= 1ll * w * h;
    cout << fixed << setprecision(12) << ans;
}

signed main() {
    Drakon();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4212kb

input:

1 1 1 1
0 0 1

output:

0.785398163397

result:

ok found '0.785398163', expected '0.785398163', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

3 50 100 100
30 10 3
40 10 7
50 90 8

output:

8.419064869325

result:

ok found '8.419064869', expected '8.419064869', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

2 5 3 4
0 0 10
3 4 15

output:

25.000000000000

result:

ok found '25.000000000', expected '25.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

1 5 6 8
3 4 1

output:

1.000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

10 6 3 3
0 0 1000
0 1 1000
1 0 1000
1 1 1000
0 2 1000
1 2 1000
2 2 1000
2 0 1000
2 1 1000
3 0 1000

output:

10000.000000000000

result:

ok found '10000.000000000', expected '10000.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4352kb

input:

10 1 1000 1000
888 437 944
769 416 49
501 904 358
489 768 761
563 549 156
124 791 843
965 282 86
240 712 351
713 135 378
374 830 77

output:

0.012575795392

result:

ok found '0.012575795', expected '0.012575795', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4276kb

input:

10 500 1000 1000
81 211 234
859 653 342
905 355 461
428 921 405
70 224 675
383 82 963
762 443 280
46 340 91
588 672 550
869 135 832

output:

2149.222068759806

result:

ok found '2149.222068760', expected '2149.222068760', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4352kb

input:

10 1000 1000 1000
775 339 418
53 697 635
380 870 528
363 703 550
240 394 755
638 938 393
372 970 735
774 789 614
816 752 551
852 291 561

output:

5660.913333863180

result:

ok found '5660.913333863', expected '5660.913333863', error '0.000000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

10 2000 1000 1000
21 118 746
894 282 609
535 912 654
926 931 609
749 530 864
166 211 826
335 975 370
446 140 383
870 110 491
409 149 653

output:

6205.000000000000

result:

ok found '6205.000000000', expected '6205.000000000', error '0.000000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 4280kb

input:

10 1 1 1000
0 949 518
0 969 783
0 939 174
1 176 8
1 866 805
0 673 221
1 433 207
0 868 283
0 636 643
0 404 210

output:

6.050707450814

result:

ok found '6.050707451', expected '6.050707451', error '0.000000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 4216kb

input:

10 500 1 1000
0 319 982
0 762 903
0 290 864
0 571 348
0 864 154
0 681 468
1 668 403
1 671 26
0 505 987
0 174 415

output:

4576.383149998889

result:

ok found '4576.383149999', expected '4576.383149999', error '0.000000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

10 1000 1 1000
1 233 171
0 416 333
1 250 928
1 799 316
1 296 504
0 596 81
0 221 314
0 847 606
1 364 891
0 666 641

output:

4785.000000000000

result:

ok found '4785.000000000', expected '4785.000000000', error '0.000000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4320kb

input:

9 2 1000 1000
500 500 1000
501 500 1000
499 500 1000
500 499 1000
500 501 1000
499 499 1000
499 501 1000
501 499 1000
501 501 1000

output:

0.113097335529

result:

ok found '0.113097336', expected '0.113097336', error '0.000000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4260kb

input:

10 1 1000 500
266 442 508
326 475 107
926 4 572
197 278 97
126 414 389
257 295 932
623 276 995
128 137 580
240 158 210
193 468 953

output:

0.033571059096

result:

ok found '0.033571059', expected '0.033571059', error '0.000000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4264kb

input:

10 500 1000 500
291 97 944
960 84 366
532 207 338
862 312 848
935 103 740
454 401 258
993 87 785
261 106 146
681 465 964
180 343 105

output:

3552.577924625556

result:

ok found '3552.577924626', expected '3552.577924626', error '0.000000000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 4188kb

input:

10 1000 1000 500
49 80 348
381 369 152
481 486 303
458 370 513
137 236 574
1000 409 64
301 402 230
344 423 652
655 145 839
177 28 191

output:

3862.906737510359

result:

ok found '3862.906737510', expected '3862.906737510', error '0.000000000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4212kb

input:

1 1 1000 1000
0 1000 1

output:

0.000000785398

result:

ok found '0.000000785', expected '0.000000785', error '0.000000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 4200kb

input:

2 1 1000 1000
0 1000 1
1000 0 1

output:

0.000001570796

result:

ok found '0.000001571', expected '0.000001571', error '0.000000000'