QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111337 | #6302. Map | ethening | AC ✓ | 3ms | 3816kb | C++17 | 2.2kb | 2023-06-06 19:55:37 | 2023-06-06 19:55:42 |
Judging History
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