QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111337#6302. MapetheningAC ✓3ms3816kbC++172.2kb2023-06-06 19:55:372023-06-06 19:55:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-06 19:55:42]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3816kb
  • [2023-06-06 19:55:37]
  • 提交

answer

#include "bits/stdc++.h"
#include <array>
#include <cassert>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const double eps = 1e-8;

template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(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); }
	bool operator==(P p) const { return fabs(x-p.x)<=eps&&fabs(y-p.y)<=eps; }
	bool operator!=(P p) const { return fabs(x-p.x)>eps||fabs(y-p.y)>eps; }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }

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

void solve() {
	Point<double> a1, b1, c1, d1;
	Point<double> a2, b2, c2, d2;
	cin >> a1.x >> a1.y >> b1.x >> b1.y >> c1.x >> c1.y >> d1.x >> d1.y;
	cin >> a2.x >> a2.y >> b2.x >> b2.y >> c2.x >> c2.y >> d2.x >> d2.y;

	Point<double> db1, dd1, db2, dd2;
	db1 = b1 - a1, dd1 = d1 - a1;
	assert(a1 + db1 + dd1 == c1);
	db2 = b2 - a2, dd2 = d2 - a2;
	assert(a2 + db2 + dd2 == c2);

	auto f = [&](const Point<double> &pt) {
		Point<double> diff = pt - a1;
		double k1 = (diff.x * dd1.y - diff.y * dd1.x) / (db1.x * dd1.y - db1.y * dd1.x);
		double k2 = (diff.x * db1.y - diff.y * db1.x) / (db1.y * dd1.x - db1.x * dd1.y);
		assert(0 <= k1 + eps && k1 - eps <= 1);
		assert(0 <= k2 + eps && k2 - eps <= 1);
		return a2 + db2 * k1 + dd2 * k2;
	};

	Point<double> S, T;
	cin >> S.x >> S.y >> T.x >> T.y;
	double k;
	int n;
	cin >> k >> n;
	vector<Point<double>> ST(n + 1), TT(n + 1);
	ST[0] = S, TT[0] = T;
	for (int i = 1; i <= n; i++) {
		ST[i] = f(ST[i - 1]);
		TT[i] = f(TT[i - 1]);
		// cout << ST[i] << " " << TT[i] << "\n";
	}

	double ans = 1e18;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i + j > n) break;
			double cur = k * (i + j);
			cur += (ST[i] - TT[j]).dist();
			ans = min(ans, cur);
		}
	}
	cout << fixed << setprecision(9) << ans << "\n";
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3596kb

input:

2
0 0 0 2 4 2 4 0
0 0 0 1 2 1 2 0
2 1 4 2
1 1
0 0 0 3 6 3 6 0
0 1 1 0 3 2 2 3
0 0 4 2
0 3

output:

1.000000000
1.227262335

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 3764kb

input:

100
-133 -128 -109 -134 -85 -38 -109 -32
-95 -37 -100 -35 -108 -55 -103 -57
-119 -130 -112 -44
2 73
5 -100 5 -8 1 -8 1 -100
1 -60 1 -14 3 -14 3 -60
3 -84 1 -20
2 53
-58 -78 -66 -78 -66 -34 -58 -34
-58 -34 -66 -34 -66 -78 -58 -78
-63 -50 -63 -37
4 54
52 -148 116 -148 116 -52 52 -52
53 -103 53 -71 101...

output:

9.500657500
12.229731079
13.000000000
17.488532900
13.341664064
7.615773106
23.409399821
7.280109889
21.280037734
59.776022093
4.123105626
79.649231007
65.069193940
14.142135624
41.824615503
16.056245185
15.672617530
21.562202374
66.272166103
21.023796042
20.880613018
24.331050121
4.123105626
55.132...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

100
-173 -113 -120 -113 -120 -115 -173 -115
-173 -115 -120 -115 -120 -113 -173 -113
-162 -114 -152 -114
99 57
6 23 -75 4 -56 -77 25 -58
0 -58 -51 -69 -62 -18 -11 -7
-22 -56 -42 -25
19 27
-98 -115 -150 -147 -158 -134 -106 -102
-150 -147 -98 -115 -106 -102 -158 -134
-103 -111 -136 -134
25 50
136 -92 1...

output:

10.000000000
25.483637976
40.224370722
18.384776311
9.219544457
18.027756377
43.114063026
52.887044352
45.541190147
55.000999975
37.000000000
12.041594579
24.331050121
18.110770276
7.563262753
2.236067977
8.236067977
14.864765109
6.324555320
62.487326567
37.656340768
4.472135955
27.294688128
49.2442...

result:

ok 100 numbers

Test #4:

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

input:

100
-12 -206 72 -188 135 -482 51 -500
19 -301 23 -301 23 -315 19 -315
88 -368 28 -248
14 87
-221 -566 -467 -566 -467 -565 -221 -565
-221 -566 -467 -566 -467 -565 -221 -565
-297 -566 -289 -566
274 18
-264 759 -339 609 -129 504 -54 654
-208 580 -208 655 -103 655 -103 580
-196 664 -211 596
8 64
-111 -3...

output:

34.246950476
8.000000000
45.926952287
135.118466540
131.973482185
40.349665954
15.321347729
77.772275035
66.738813036
8.000266655
116.806446032
12.588290016
170.785630266
131.962750429
8.738089975
17.464249197
15.499659843
26.069836146
258.073632903
17.745735330
25.750000000
98.310731866
15.58053738...

result:

ok 100 numbers

Test #5:

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

input:

100
-235 -704 133 -704 133 -720 -235 -720
-224 -712 -40 -712 -40 -704 -224 -704
15 -711 76 -718
4 74
-467 574 -475 596 -123 724 -115 702
-274 662 -270 652 -430 588 -434 598
-458 588 -241 657
15 31
380 -3 532 -343 787 -229 635 111
503 -71 639 -163 708 -61 572 31
533 -189 613 -137
3 58
-460 -7 -488 -7...

output:

31.350081433
51.967632321
21.468697928
38.837932076
84.248187428
77.929455278
47.000000000
74.115493726
86.467104880
35.114099732
3.605551275
97.416631024
24.606056966
56.773359433
6.998534619
13.453624047
150.786165723
65.855903304
26.172504657
128.035151423
276.001811588
86.996683927
70.910283375
...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 3804kb

input:

100
-1201 2822 -1197 2814 -3437 1694 -3441 1702
-3119 1860 -3117 1856 -1997 2416 -1999 2420
-1419 2709 -2491 2174
48 76
-2515 285 -2547 306 -1308 2194 -1276 2173
-2255 683 -2260 686 -2083 981 -2078 978
-1572 1753 -1392 2015
121 28
-1216 1209 -1498 -1141 -1598 -1129 -1316 1221
-1494 -823 -1494 -447 -...

output:

264.055863533
290.425700451
258.282400313
743.737184764
341.052781839
400.566683662
172.040799341
27.770894610
294.825880152
508.065910689
501.781825099
666.805068967
180.069431054
193.610433603
1507.002986062
25.019992006
81.748007498
346.028984290
105.478668700
233.004795442
109.283851272
870.0051...

result:

ok 100 numbers

Test #7:

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

input:

100
1411 -2755 603 -3563 623 -3583 1431 -2775
716 -3477 1120 -3073 1110 -3063 706 -3467
1210 -2959 1339 -2830
2319 39
4528 -3417 4286 -4055 1908 -3153 2150 -2515
2094 -2892 2094 -3090 2832 -3090 2832 -2892
2257 -2993 4389 -3736
17 22
-180 -1673 -2172 -3665 -2164 -3673 -172 -1681
-284 -1792 -2027 -35...

output:

182.433549546
96.880923054
530.330085890
44.011362169
64.313365366
7.392893666
34.567810207
148.850160743
350.338135916
329.225162780
68.864765109
32.824383175
244.695729427
685.968837712
141.362747996
1601.789826723
6.885591146
70.671460706
5.179654429
277.064974329
49.481667656
391.808626755
172.0...

result:

ok 100 numbers

Test #8:

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

input:

100
11928 -18111 8928 -17411 11056 -8291 14056 -8991
11043 -10811 10793 -10111 12921 -9351 13171 -10051
10491 -14092 11923 -12413
10 92
11869 -4371 3539 5429 1299 3525 9629 -6275
8302 -3064 3647 2571 4935 3635 9590 -2000
2384 2680 3466 2644
181 91
4001 -10187 4001 -10897 9 -10897 9 -10187
838 -10629...

output:

87.479657003
977.209322821
94.486325059
307.006514589
1245.629559701
532.000000000
369.048777264
19.554024317
1509.000000000
275.094267211
4242.193351515
465.656251409
3478.304242060
1754.356007200
1804.466927586
21.353142661
415.415534625
1526.434407369
3853.602936508
3165.826590324
1671.019150100
...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 3ms
memory: 3816kb

input:

100
10303 -4099 19487 -8131 19703 -7639 10519 -3607
18394 -7495 18842 -7271 18854 -7295 18406 -7519
15852 -6248 15950 -6389
38 10
13132 -3411 17416 3393 15634 4515 11350 -2289
13143 -873 15411 3411 16533 2817 14265 -1467
16515 2577 16017 1561
198 94
-5480 10872 -6297 11294 -11361 1490 -10544 1068
-1...

output:

84.574886489
999.689277678
6231.529667746
550.947886095
182.544124659
5374.296791209
825.725781097
1653.207429169
2777.109648537
166.653023806
1747.004579273
651.111357603
242.210006732
34.266895846
286.790864569
2405.246628921
2133.342213523
1310.978131574
48.466483264
464.432837829
401.842008755
6...

result:

ok 100 numbers

Test #10:

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

input:

100
0 -30 84 12 126 -72 42 -114
0 -30 84 12 126 -72 42 -114
91 -41 100 -55
96 93
168 110 148 150 48 100 68 60
48 100 68 60 168 110 148 150
61 96 102 90
8 2
-123 129 -60 174 -15 111 -78 66
-15 111 -78 66 -123 129 -60 174
-44 115 -104 132
27 3
27 42 15 54 -75 -36 -63 -48
-63 -48 -75 -36 15 54 27 42
-4...

output:

16.643316977
41.436698710
39.206555616
11.180339887
49.729267037
26.925824036
50.931326313
10.294055820
117.885537705
8.602325267
48.466483264
21.095023110
24.038404810
16.000000000
48.548944376
26.061756860
39.539832078
10.770329614
20.973213749
7.280109889
56.293871780
66.644826477
20.649110641
25...

result:

ok 100 numbers

Test #11:

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

input:

100
9725 6731 9725 11971 14965 11971 14965 6731
9725 6731 9725 11971 14965 11971 14965 6731
10293 11185 10445 9833
488 10
3833 -4831 6913 -4271 8443 -12686 5363 -13246
6913 -4271 3833 -4831 5363 -13246 8443 -12686
5209 -4960 7133 -6409
1 88
-5891 -6066 -8365 -6066 -8365 -8540 -5891 -8540
-8365 -6066...

output:

1360.517548582
2119.674780140
1638.601494195
144.699689011
1706.299211745
2671.668018299
1442.324859385
2909.931270666
5311.386353863
7894.844203656
2950.721437208
1405.197279587
8052.785977536
436.084854128
1910.190147124
1597.007827157
8923.079345159
3776.233573284
6300.141744437
1071.688854099
39...

result:

ok 100 numbers

Test #12:

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

input:

100
1432065 -1359744 1432065 -1359796 610089 -1359796 610089 -1359744
610089 -1359744 610089 -1359796 1432065 -1359796 1432065 -1359744
1413145 -1359747 670086 -1359765
306 12
-630899 -570942 344981 -570942 344981 -567164 -630899 -567164
-630899 -567164 344981 -567164 344981 -570942 -630899 -570942
...

output:

41383.003943813
344430.708764477
597464.947160122
57512.000021251
180112.504983949
254594.189465464
13301.834367631
246235.741341504
17086.953736696
168329.001188149
580568.278437601
120047.475965045
24722.575937794
252882.798719090
366.882341146
108187.768573337
2882.075116051
31046.363349948
219.7...

result:

ok 100 numbers

Test #13:

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

input:

100
-240497 1168822 -365542 931192 504344 473443 629389 711073
226221 683190 167481 688085 185400 903113 244140 898218
-192129 1110656 34450 941656
2 25
1729381 25950 1512625 519672 1528369 526584 1745125 32862
1536820 492965 1580974 388601 1584302 390009 1540148 494373
1660204 207517 1601591 344571...

output:

33.523773639
126504.999518609
57518.293697333
318943.663702542
169769.250005669
1497.133893067
23459.324991965
853.347816095
28.351411846
7526.106524036
36705.816569040
575.015321675
4025.084882225
31458.023666467
316549.014556988
52928.370889344
136396.393291486
10642.361627197
114174.545328633
940...

result:

ok 100 numbers

Test #14:

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

input:

100
-889209 606569 -191736 1436894 638589 739421 -58884 -90904
-58884 -90904 638589 739421 -191736 1436894 -889209 606569
-486300 891465 -464854 988546
79 18
-1226546 957048 -712144 1926170 -590407 1861553 -1104809 892431
-712144 1926170 -1226546 957048 -1104809 892431 -590407 1861553
-807239 146415...

output:

99421.584562911
404181.388824374
311311.528917578
271785.624537060
319158.191839094
77725.025543495
103690.241569290
33781.004277552
16708.608350189
262422.768227149
176381.843093330
159818.483940375
451836.634220814
291664.040180888
406095.266612405
591425.317986980
728801.794638981
271491.02911514...

result:

ok 100 numbers