QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696587#8246. Garden of Thornscrimson231AC ✓0ms4332kbC++236.6kb2024-10-31 23:40:082024-10-31 23:40:08

Judging History

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

  • [2024-10-31 23:40:08]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4332kb
  • [2024-10-31 23:40:08]
  • 提交

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'