QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#343101 | #8246. Garden of Thorns | ElTeeran_ElHayga# | AC ✓ | 1ms | 4352kb | C++20 | 4.9kb | 2024-03-01 22:18:39 | 2024-03-01 22:18:41 |
Judging History
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();
}
}
詳細信息
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'