QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696587 | #8246. Garden of Thorns | crimson231 | AC ✓ | 0ms | 4332kb | C++23 | 6.6kb | 2024-10-31 23:40:08 | 2024-10-31 23:40:08 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
typedef long long ll;
typedef double ld;
typedef std::vector<ld> Vld;
const ld INF = 1e17;
const ld TOL = 1e-13;
const ld PI = acosl(-1);
const int LEN = 25;
inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }
inline bool eq(const ld& u, const ld& v) { return zero(u - v); }
inline ll sq(const ll& x) { return x * x; }
inline ld norm(ld th) { while (th < 0) th += 2 * PI; while (sign(th - 2 * PI) >= 0) th -= 2 * PI; return th; }
inline ld fit(const ld& x, const ld& lo, const ld& hi) { return std::min(hi, std::max(lo, x)); }
#define si lo
#define theta hi
#define LINE 1
#define CIRCLE 2
struct Pos {
ld x, y;
Pos(ld x_ = 0, ld y_ = 0) : x(x_), y(y_) {}
bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
ld operator * (const Pos& p) const { return x * p.x + y * p.y; }
ld operator / (const Pos& p) const { return x * p.y - y * p.x; }
Pos rot(const ld& the) const { return Pos(x * cos(the) - y * sin(the), x * sin(the) + y * cos(the)); }
ld Euc() const { return x * x + y * y; }
ld mag() const { return sqrt(Euc()); }
ld rad() const { return norm(atan2(y, x)); }
inline friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
inline friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
}; const Pos O = Pos(0, 0);
typedef std::vector<Pos> Polygon;
ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { return sign(cross(d1, d2, d3)); }
ld dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
ld dot(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) * (d4 - d3); }
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && sign(dot(d1, d3, d2)) >= 0; }
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && sign(dot(d1, d3, d2)) > 0; }
Pos intersection(const Pos& p1, const Pos& p2, const Pos& q1, const Pos& q2) { ld a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2); return (p1 * a2 + p2 * a1) / (a1 + a2); }
bool inner_check(const Polygon& H, const Pos& p) {
int sz = H.size();
for (int i = 0; i < sz; i++) {
int i1 = (i + 1) % sz;
if (ccw(H[i], H[i1], p) < 0) return 0;
}
return 1;
}
struct Seg {
Pos s, e;
Seg(Pos s_ = Pos(), Pos e_ = Pos()) : s(s_), e(e_) {}
Pos p(const ld& rt) const { return s + (e - s) * rt; }
ld green(const ld& lo, const ld& hi) const {
ld d = hi - lo;
ld ratio = (lo + hi) * .5;
Pos m = p(ratio);
return m.y * d * (s.x - e.x);
}
};
struct Circle {
Pos c;
int r;
Circle(Pos c_ = Pos(), int r_ = 0) : c(c_), r(r_) {}
bool operator == (const Circle& q) const { return c == q.c && r == q.r; }
bool operator < (const Circle& q) const { return c == q.c ? r < q.r : c < q.c; }
bool operator < (const Pos& p) const { return sign(r - (c - p).mag()) < 0; }
bool operator >= (const Pos& p) const { return sign(r - (c - p).mag()) >= 0; }
bool outside(const Circle& q) const { return sign((c - q.c).Euc() - sq((ll)r + q.r)) >= 0; }
Pos p(const ld& t) const { return c + Pos(r, 0).rot(t); }
ld rad(const Pos& p) const { return (p - c).rad(); }
ld area(const ld& lo, const ld& hi) const { return (hi - lo) * r * r * .5; }
ld green(const ld& lo, const ld& hi) const {
Pos s = Pos(cos(lo), sin(lo)), e = Pos(cos(hi), sin(hi));
ld fan = area(lo, hi);
Pos m = c + (s + e) * r * (ld).5;
ld tz = (cos(lo) - cos(hi)) * m.y * r;
return fan + tz - (s / e) * r * r * (ld).5;
}
};
typedef std::vector<Circle> Disks;
Vld circle_line_intersections(const Seg& l, const Circle& q, const int& t = LINE) {
//https://math.stackexchange.com/questions/311921/get-location-of-vector-circle-intersection
Pos s = l.s, e = l.e;
Pos vec = e - s;
Pos OM = s - q.c;
ld a = vec.Euc();
ld b = vec * OM;
ld c = OM.Euc() - q.r * q.r;
ld J = b * b - a * c;
if (J < -TOL) return {};
ld det = sqrt(std::max((ld)0, J));
ld lo = (-b - det) / a;
ld hi = (-b + det) / a;
Vld ret;
if (t == LINE) {
if (0 < lo && lo < 1) ret.push_back(lo);
if (zero(det)) return ret;
if (0 < hi && hi < 1) ret.push_back(hi);
}
else {//circle
auto the = [&](ld rt) { return q.rad(s + (e - s) * rt); };
if (-TOL < lo && lo < 1 + TOL) ret.push_back(the(lo));
if (zero(det)) return ret;
if (-TOL < hi && hi < 1 + TOL) ret.push_back(the(hi));
}
return ret;
}
struct Arc {
ld lo, hi;
Arc(ld l_ = 0, ld h_ = 0) : lo(l_), hi(h_) {}
bool operator < (const Arc& a) const { return zero(lo - a.lo) ? hi < a.hi : lo < a.lo; }
};
typedef std::vector<Arc> Arcs;
void solve() {
std::cin.tie(0)->sync_with_stdio(0);
std::cout.tie(0);
std::cout << std::fixed;
std::cout.precision(15);
int N, V[LEN], R, W, H;
std::cin >> N >> R >> W >> H;
Polygon P(N); for (int i = 0; i < N; i++) std::cin >> P[i] >> V[i];
int SQ = W * H, sz;
ld ret = 0;
Pos p0 = O, p1 = Pos(W, 0), p2 = Pos(W, H), p3 = Pos(0, H);
Polygon B = { p0, p1, p2, p3 };
for (int i = 0; i < N; i++) {
ld A = 0;
Circle c = Circle(P[i], R);
Vld tmp = { 0 };
for (int j = 0; j < 4; j++) {
Seg s = Seg(B[j], B[(j + 1) % 4]);
Vld xx = circle_line_intersections(s, c, CIRCLE);
for (const ld& x : xx) tmp.push_back(x);
xx = circle_line_intersections(s, c, LINE);
Vld v = { 0, 1 };
for (const ld& x : xx) v.push_back(x);
std::sort(v.begin(), v.end());
sz = v.size();
for (int k = 0; k < sz - 1; k++) {
if (eq(v[k], v[k + 1])) continue;
ld m = (v[k] + v[k + 1]) * .5;
Pos mid = s.p(m);
if (c >= mid) A += s.green(v[k], v[k + 1]);
}
}
std::sort(tmp.begin(), tmp.end());
tmp.push_back(2 * PI);
sz = tmp.size();
for (int j = 0; j < sz - 1; j++) {
if (eq(tmp[j], tmp[j + 1])) continue;
ld m = (tmp[j] + tmp[j + 1]) * .5;
Pos mid = c.p(m);
if (inner_check(B, mid)) A += c.green(tmp[j], tmp[j + 1]);
}
ret += A / SQ * V[i];
}
std::cout << ret << "\n";
return;
}
int main() { solve(); return 0; }//boj31304
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4200kb
input:
1 1 1 1 0 0 1
output:
0.785398163397448
result:
ok found '0.785398163', expected '0.785398163', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4320kb
input:
3 50 100 100 30 10 3 40 10 7 50 90 8
output:
8.419064869324508
result:
ok found '8.419064869', expected '8.419064869', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4312kb
input:
2 5 3 4 0 0 10 3 4 15
output:
25.000000000000000
result:
ok found '25.000000000', expected '25.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4312kb
input:
1 5 6 8 3 4 1
output:
1.000000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4156kb
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.000000000000000
result:
ok found '10000.000000000', expected '10000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4072kb
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.012575795392320
result:
ok found '0.012575795', expected '0.012575795', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4324kb
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.222068759805552
result:
ok found '2149.222068760', expected '2149.222068760', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4324kb
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.913333863180014
result:
ok found '5660.913333863', expected '5660.913333863', error '0.000000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4104kb
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.000000000000000
result:
ok found '6205.000000000', expected '6205.000000000', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4232kb
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.050707450813125
result:
ok found '6.050707451', expected '6.050707451', error '0.000000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4332kb
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.383149998793670
result:
ok found '4576.383149999', expected '4576.383149999', error '0.000000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4004kb
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.000000000000000
result:
ok found '4785.000000000', expected '4785.000000000', error '0.000000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4204kb
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.113097335529233
result:
ok found '0.113097336', expected '0.113097336', error '0.000000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 4004kb
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.033571059096261
result:
ok found '0.033571059', expected '0.033571059', error '0.000000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4324kb
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.577924625556534
result:
ok found '3552.577924626', expected '3552.577924626', error '0.000000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 4316kb
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.906737510359562
result:
ok found '3862.906737510', expected '3862.906737510', error '0.000000000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4200kb
input:
1 1 1000 1000 0 1000 1
output:
0.000000785398163
result:
ok found '0.000000785', expected '0.000000785', error '0.000000000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4260kb
input:
2 1 1000 1000 0 1000 1 1000 0 1
output:
0.000001570796327
result:
ok found '0.000001571', expected '0.000001571', error '0.000000000'