QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54283#4573. Global Warmingnot_so_organic#AC ✓407ms45952kbC++233.8kb2022-10-07 19:10:022022-10-07 19:10:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-07 19:10:04]
  • 评测
  • 测评结果:AC
  • 用时:407ms
  • 内存:45952kb
  • [2022-10-07 19:10:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using D = long double;
struct P{
	LL x, y, z;
	bool operator < (const P& p) const {
		return z == p.z ? (
			y == p.y ? x > p.x : y > p.y
		) : z > p.z;
	}
};
struct F{
	D a, b, c;
	F(D a = 0, D b = 0, D c = 0) : a(a), b(b), c(c) {
	}
	F(const P& p){
		a = p.x;
		b = p.y;
		c = p.z;
	}
	F operator * (D k) const {
		return {a * k, b * k, c * k};
	}
	F operator + (const F& f) const {
		return {a + f.a, b + f.b, c + f.c};
	}
	F operator - (const F& f) const {
		return {a - f.a, b - f.b, c - f.c};
	}
	F& operator += (const F& f) {
		a += f.a;
		b += f.b;
		c += f.c;
		return *this; 
	}
	F& operator -= (const F& f) {
		a -= f.a;
		b -= f.b;
		c -= f.c;
		return *this; 
	}
	D operator()(D x) {
		return (a * x + b) * x + c;
	}
	F cross(const F& f) const {
		return {
			a * f.b - b * f.a,
			b * f.c - c * f.b,
			c * f.a - a * f.c
		};
	}
	D norm() const{
		return sqrt(a * a + b * b + c * c);
	}
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);
	int n;
	cin >> n;
	vector<P> p(n);
	for (auto& [x, y, z] : p)
		cin >> x >> y >> z;
	int m;
	cin >> m;
	vector t(m, vector<int>(3));
	vector df(m, vector<F>(3));
	vector G(n, vector<vector<int>>(3));
	for (int i = 0; i < m; i += 1) {
		for (int& tj : t[i]) {
			cin >> tj;
			tj -= 1;
		}
		sort(t[i].begin(), t[i].end(), [&](int x, int y) {
			return p[x] < p[y];
		});
		vector<F> tp(3);
		for (int j = 0; j < 3; j += 1) tp[j] = p[t[i][j]];
		D s = (tp[1] - tp[0]).cross(tp[2] - tp[0]).norm() / 2;
		if (tp[0].c == tp[2].c)
			df[i][0].c = s;
		else if (tp[0].c == tp[1].c) {
			D dh = tp[1].c - tp[2].c;
			D a = s / (dh * dh);
			df[i][1] = {-a, 2 * a * tp[2].c, s - a * tp[2].c * tp[2].c};
			df[i][2] = {0, 0, s};
			df[i][2] -= df[i][1];
		}
		else if (tp[1].c == tp[2].c) {
			D dh = tp[0].c - tp[1].c;
			D a = s / (dh * dh);
			df[i][0] = {a, -2 * a * tp[0].c, a * tp[0].c * tp[0].c};
			df[i][1] = {0, 0, s};
			df[i][1] -= df[i][0];
		}
		else {
			D h1 = tp[0].c - tp[1].c;
			D h2 = tp[1].c - tp[2].c;
			F f = tp[0] + (tp[2] - tp[0]) * (h1 / (h1 + h2));
			D s1 = (tp[1] - tp[0]).cross(f - tp[0]).norm() / 2;
			D s2 = (tp[1] - tp[2]).cross(f - tp[2]).norm() / 2;
			D a1 = s1 / (h1 * h1);
			D a2 = s2 / (h2 * h2);
			df[i][0] = {a1, -2 * a1 * tp[0].c, a1 * tp[0].c * tp[0].c};
			df[i][1] = {-a2, 2 * a2 * tp[2].c, s - a2 * tp[2].c * tp[2].c};
			df[i][2] = {0, 0, s};
			df[i][2] -= df[i][1];
			df[i][1] -= df[i][0];
		}
		for (int j = 0; j < 3; j += 1)
			G[t[i][j]][j].push_back(i);
	}
	int q;
	cin >> q;
	vector<LL> h(q);
	vector<int> pq(q), f(n), pv(n + q), qv(q);
	vector<vector<int>> Q(n);
	for (int i = 0; i < q; i += 1) {
		cin >> h[i] >> pq[i];
		qv[i] = i;
		pv[n + i] = n + i;
		pq[i] -= 1;
		Q[pq[i]].push_back(i);
	}
	vector<D> ans(q, -1);
	vector<F> cf(n);
	for (int i = 0; i < n; i += 1)
		pv[i] = f[i] = i;
	function<int(int)> ff = [&](int u) {
		return f[u] == u ? u : f[u] = ff(f[u]);
	};
	sort(pv.begin(), pv.end(), [&](int x, int y){
		LL px = x >= n ? h[x - n] : p[x].z;
		LL py = y >= n ? h[y - n] : p[y].z;
		return px != py ? px > py : x > y;
	});
	for (int i : pv) {
		if (i < n) {
			int u = i;
			for (int j = 0; j < 3; j += 1) {
				for (int x : G[i][j]) {
					for (int y = 0; y < j; y += 1) {
						int v = t[x][y];
						int fu = ff(u), fv = ff(v);
						if (fu != fv) {
							f[fu] = fv;
							cf[fv] += cf[fu];
						}
					}
					int fu = ff(u);
					cf[fu] += df[x][j];
				}
			}
		}
		else {
			i -= n;
			if (h[i] < p[pq[i]].z) {
				int u = ff(pq[i]);
				ans[i] = cf[u](h[i]);
			}
			i += n;
		}
	}
	for (D d : ans)
		if (d < -0.9) cout << "-1\n";
		else cout << d << "\n";
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3708kb

input:

5
0 0 0
2 0 0
2 2 0
0 2 0
1 1 4
4
1 2 5
2 3 5
3 4 5
4 1 5
7
0 1
0 5
1 5
2 5
3 5
4 5
5 5

output:

-1
16.49242250247064219860
9.27698765763973623617
4.12310562561766054922
1.03077640640441513774
-1
-1

result:

ok 7 numbers

Test #2:

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

input:

16
0 5 0
1 2 0
2 5 5
3 7 0
4 0 0
4 3 5
5 5 1
6 2 0
6 6 5
7 4 4
7 8 0
8 2 0
9 4 0
4 6 4
6 3 3
2 4 5
22
11 10 9
12 8 10
2 6 5
9 10 7
8 15 6
16 3 6
15 6 7
7 3 14
8 10 15
11 13 10
16 6 2
12 10 13
10 7 15
16 3 2
3 4 1
14 7 9
11 9 4
3 6 7
5 6 8
14 4 3
3 1 2
9 4 14
7
0 7
1 7
1 16
2 10
3 9
4 16
5 16

output:

120.48340535430632507186
-1
93.92989522248478349159
68.18191966353693998087
40.91856147414833069081
11.06744179092106980522
-1

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

9
0 0 0
0 1 0
0 2 0
1 0 0
1 1 10
1 2 0
2 0 0
2 1 0
2 2 0
8
4 8 5
5 9 8
8 4 7
1 2 5
2 6 3
9 6 5
6 2 5
1 5 4
5
9 5
0 5
3 5
3 5
2 5

output:

0.34277198120999605863
34.27719812099960574464
16.79582707928980681543
16.79582707928980681543
21.93740679743974767747

result:

ok 5 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

100
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
1 0 0
1 1 3
1 2 3
1 3 3
1 4 3
1 5 3
1 6 3
1 7 3
1 8 3
1 9 0
2 0 0
2 1 3
2 2 1
2 3 4
2 4 5
2 5 5
2 6 5
2 7 5
2 8 3
2 9 0
3 0 0
3 1 3
3 2 4
3 3 5
3 4 7
3 5 7
3 6 6
3 7 5
3 8 3
3 9 0
4 0 0
4 1 1
4 2 4
4 3 6
4 4 8
4 5 6
4 6 3
4 7 5
4 8 3
4 ...

output:

81.67041375455158742219
183.36679393306701510435
33.49069264698641297529
183.36679393306701510435
183.36679393306701510435

result:

ok 5 numbers

Test #5:

score: 0
Accepted
time: 298ms
memory: 44564kb

input:

49729
0 0 0
0 1234 0
0 2468 0
0 3702 0
0 4936 0
0 6170 0
0 7404 0
0 8638 0
0 9872 0
0 11106 0
0 12340 0
0 13574 0
0 14808 0
0 16042 0
0 17276 0
0 18510 0
0 19744 0
0 20978 0
0 22212 0
0 23446 0
0 24680 0
0 25914 0
0 27148 0
0 28382 0
0 29616 0
0 30850 0
0 32084 0
0 33318 0
0 34552 0
0 35786 0
0 3702...

output:

28336022114792.79007530212402343750
-1
9067597268.20159996673464775085
29490770935284.62855911254882812500
21397921724095.22158241271972656250
-1
414425634047.63759446144104003906
-1
-1
-1
-1
-1
30771157933943.65496063232421875000
-1
25468403653000.28624153137207031250
-1
-1
16769145554603.786490440...

result:

ok 100000 numbers

Test #6:

score: 0
Accepted
time: 379ms
memory: 44736kb

input:

49729
0 0 0
0 1234 0
0 2468 0
0 3702 0
0 4936 0
0 6170 0
0 7404 0
0 8638 0
0 9872 0
0 11106 0
0 12340 0
0 13574 0
0 14808 0
0 16042 0
0 17276 0
0 18510 0
0 19744 0
0 20978 0
0 22212 0
0 23446 0
0 24680 0
0 25914 0
0 27148 0
0 28382 0
0 29616 0
0 30850 0
0 32084 0
0 33318 0
0 34552 0
0 35786 0
0 3702...

output:

29353956709678.41348075866699218750
31503581108233.60822296142578125000
2451504799.08534144610166549683
30277327205891.44835090637207031250
30263230103493.75245857238769531250
31519100793321.26255035400390625000
31472715345694.00540542602539062500
26006398827719.23224639892578125000
30685636802105.0...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 381ms
memory: 45952kb

input:

49729
0 0 0
0 1234 0
0 2468 0
0 3702 0
0 4936 0
0 6170 0
0 7404 0
0 8638 0
0 9872 0
0 11106 0
0 12340 0
0 13574 0
0 14808 0
0 16042 0
0 17276 0
0 18510 0
0 19744 0
0 20978 0
0 22212 0
0 23446 0
0 24680 0
0 25914 0
0 27148 0
0 28382 0
0 29616 0
0 30850 0
0 32084 0
0 33318 0
0 34552 0
0 35786 0
0 3702...

output:

572960766753.56390643119812011719
333954833128.79015082120895385742
781430007202.26097732782363891602
485385379872.38139396905899047852
551112725934.58813095092773437500
167358330713.08261156082153320312
925545375390.33722335100173950195
884146260755.75288367271423339844
868595978493.302268505096435...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 378ms
memory: 44612kb

input:

49729
0 0 0
0 1234 0
0 2468 0
0 3702 0
0 4936 0
0 6170 0
0 7404 0
0 8638 0
0 9872 0
0 11106 0
0 12340 0
0 13574 0
0 14808 0
0 16042 0
0 17276 0
0 18510 0
0 19744 0
0 20978 0
0 22212 0
0 23446 0
0 24680 0
0 25914 0
0 27148 0
0 28382 0
0 29616 0
0 30850 0
0 32084 0
0 33318 0
0 34552 0
0 35786 0
0 3702...

output:

897647.21861104938216158189
41601577.18058780183127964847
57963769155.75516934320330619812
2006308.54905005876935319975
66648786362.24849710613489151001
72258674159.19144428521394729614
72258674159.19144428521394729614
122697223.20800586161203682423
74912964693.41987413913011550903
66648786362.24849...

result:

ok 100000 numbers

Test #9:

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

input:

12
0 0 0
0 5 0
5 5 0
5 0 0
1 1 2
1 4 2
4 4 2
4 1 2
2 2 0
2 3 0
3 3 0
3 2 0
18
10 9 11
11 6 7
5 6 10
5 8 4
12 11 9
6 2 1
10 9 5
8 5 9
1 5 4
8 7 12
6 5 1
8 9 12
10 11 6
8 4 3
7 2 6
12 7 11
3 7 8
2 7 3
1
0 5

output:

53.66563145999495271221

result:

ok found '53.6656315', expected '53.6656315', error '0.0000000'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3876kb

input:

12
0 0 0
0 5 0
5 5 0
5 0 0
1 1 2
1 4 2
4 4 2
4 1 2
2 2 4
2 3 4
3 3 4
3 2 4
18
10 9 11
11 6 7
5 6 10
5 8 4
12 11 9
6 2 1
10 9 5
8 5 9
1 5 4
8 7 12
6 5 1
8 9 12
10 11 6
8 4 3
7 2 6
12 7 11
3 7 8
2 7 3
1
0 5

output:

54.66563145999495271221

result:

ok found '54.6656315', expected '54.6656315', error '0.0000000'

Test #11:

score: 0
Accepted
time: 367ms
memory: 45616kb

input:

50000
1000000 0 0
-499999 866025 0
-500000 -866025 0
916495 24153 20321
315147 394537 769870
651467 -179658 360140
233942 -76261 740341
838791 87259 126557
303017 392128 779543
941754 -6365 19430
124786 -492497 772546
-217751 -238771 297571
-23711 323594 636099
275839 -188254 736640
928586 29943 345...

output:

43430624283954.15934753417968750000
12858380405517.49036598205566406250
93482365765.11637914180755615234
43321845735814.34445571899414062500
13336447877237.21238803863525390625
17404343997.38795579969882965088
34467363242303.31440734863281250000
43405094547561.58883285522460937500
39131002840237.256...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 407ms
memory: 45736kb

input:

50000
1000000 0 0
-499999 866025 0
-500000 -866025 0
602988 91211 216221
455493 -119881 429853
-399458 274661 465649
-291227 492885 333531
305005 -199848 590862
117889 393387 758345
41752 476626 673156
-259925 -672385 311200
80905 256085 768625
-462678 6550 279723
451465 118984 371649
831927 -20281 ...

output:

2322831875036.94566321372985839844
25855254818251.73069763183593750000
25786991781147.48773765563964843750
2942524730858.32297587394714355469
15254374353.86338156461715698242
22617750383708.09581947326660156250
15515939596317.95342445373535156250
16179419706100.70890331268310546875
22057567140769.47...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 393ms
memory: 44980kb

input:

50000
1000000 0 0
-499999 866025 0
-500000 -866025 0
-406181 -463113 5565
360070 -254117 327382
-435002 -370999 150939
-432026 -264882 736215
-431996 -315399 763809
-34186 74054 210200
-495547 600420 422265
-442146 -482250 335082
263246 -379485 810689
-481286 373221 471520
-184475 -578243 257916
804...

output:

1796860254418.82000148296356201172
242290432739284.39671325683593750000
382427698314815.89276123046875000000
16895448115472.12430000305175781250
175161422.56783631001599133015
75351167646370.30064392089843750000
203278352090659.06983947753906250000
119637497847007.95452117919921875000
1480483568469....

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 294ms
memory: 45368kb

input:

50000
14233 -482924 503223
-619853 42191 836937
933219 -630695 981538
571855 -506938 928685
659572 -89936 331112
396383 -935548 714968
-110061 -834487 204893
-327590 159339 192510
-773712 -294863 371202
716312 804785 562164
124500 -362150 635977
383472 -527493 368927
283452 827395 515767
-9790 -3693...

output:

-1
11677533560170376.77539062500000000000
-1
2327625177955293.61914062500000000000
10593333095221017.03125000000000000000
12710524468264703.49414062500000000000
-1
2019951545369946.87890625000000000000
-1
12445254039687682.56933593750000000000
9559056375926237.57812500000000000000
11419834997464115....

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 368ms
memory: 44820kb

input:

50000
-884634 740598 254245
-848157 107291 379205
814379 -969178 47711
266076 562979 729407
429003 -174495 625696
-85197 -456582 198461
-817626 -664002 629444
-865129 -789609 237813
737831 724197 617606
-621008 997403 210152
-849460 946458 817676
567198 934117 897456
883783 -316320 844007
-837482 -1...

output:

15574462096016379.91308593750000000000
10053475564194189.83496093750000000000
15575656264873924.56054687500000000000
15578451364341851.72851562500000000000
15475194319450041.02343750000000000000
15583907372907838.84863281250000000000
14918882475507763.79394531250000000000
15573693366188284.595703125...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 371ms
memory: 45108kb

input:

50000
547614 -545758 429052
227222 -204199 714473
-67322 415880 921974
-744631 -943094 184202
-859827 785569 226236
-614105 -629950 477041
527507 -10999 798771
-122047 -781292 568327
-78172 745536 478104
-495749 -687586 537199
-539763 800565 356415
-315477 -720985 375379
-697970 -694551 384093
22027...

output:

6791253380611264.56933593750000000000
6444948610720401.81542968750000000000
6906763735824260.35595703125000000000
6698124103036643.17919921875000000000
6404745518809350.40478515625000000000
3935529254.33567869663238525391
291733933253848.05087280273437500000
6905207700103069.12353515625000000000
657...

result:

ok 100000 numbers