QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#328156 | #6302. Map | C1942huangjiaxu | AC ✓ | 1ms | 3912kb | C++14 | 1.3kb | 2024-02-15 17:39:36 | 2024-02-15 17:39:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int T,n,k;
struct node{
double x,y;
node operator -(node b){
return {x-b.x,y-b.y};
}
node operator +(node b){
return {x+b.x,y+b.y};
}
double operator *(node b){
return x*b.x+y*b.y;
}
double dis(){
return sqrt(x*x+y*y);
}
void read(){
scanf("%lf%lf",&x,&y);
}
}s,t,p[4],a1,a2,a3,b1,b2,b3,f[N],g[N];
bool rv;
double cros(node a,node b){
return a.x*b.y-a.y*b.x;
}
double dis(node a,node b){
return (a-b).dis();
}
node F(node a){
a=a-a1;
if(a.dis()<1e-9)return b1;
double cs=min(1.0,a*a2/a.dis()/a2.dis()),sn=sqrt(1-cs*cs);
if(rv==(cros(a,a2)<0))sn=-sn;
node b={b2.x*cs-b2.y*sn,b2.x*sn+b2.y*cs};
double dt=a.dis()/a2.dis();
b.x*=dt,b.y*=dt;
return b1+b;
}
void solve(){
for(int i=0;i<4;++i)p[i].read();
a1=p[0],a2=p[1]-p[0],a3=p[3]-p[0];
for(int i=0;i<4;++i)p[i].read();
b1=p[0],b2=p[1]-p[0],b3=p[3]-p[0];
rv=(cros(a2,a3)>0)!=(cros(b2,b3)>0);
s.read(),t.read();
scanf("%d%d",&k,&n);
f[0]=s,g[0]=t;
for(int i=1;i<=n;++i)f[i]=F(f[i-1]),g[i]=F(g[i-1]);
double ans=dis(s,t);
for(int i=0;i<=n;++i)for(int j=0;j+i<=n;++j)ans=min(ans,(i+j)*k+dis(f[i],g[j]));
printf("%.12lf\n",ans);
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
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.000000000000 1.227262335243
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3860kb
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.500657499742 12.229731078922 13.000000000000 17.488532900375 13.341664064126 7.615773105864 23.409399821439 7.280109889281 21.280037734084 59.776022092579 4.123105625618 79.649231006960 65.069193939990 14.142135623731 41.824615503480 16.056245184897 15.672617529929 21.562202374203 66.272166103124 ...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3776kb
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.000000000000 25.483637975584 40.224370722238 18.384776310850 9.219544457293 18.027756377320 43.114063026280 52.887044352349 45.541190146943 55.000999975001 37.000000000000 12.041594578792 24.331050121193 18.110770276275 7.563262753280 2.236067977500 8.236067977500 14.864765108873 6.324555320337 6...
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3852kb
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.246950475544 8.000000000000 45.926952286843 135.118466539552 131.973482184869 40.349665953953 15.321347728713 77.772275035020 66.738813035899 8.000266654816 116.806446031673 12.588290015616 170.785630266286 131.962750429094 8.738089975160 17.464249196573 15.499659842874 26.069836145638 258.073632...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3912kb
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.350081433009 51.967632320938 21.468697928147 38.837932076468 84.248187428308 77.929455278476 47.000000000000 74.115493725913 86.467104880422 35.114099732159 3.605551275464 97.416631023660 24.606056965765 56.773359432724 6.998534619415 13.453624047074 150.786165723470 65.855903304108 26.1725046566...
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3776kb
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.055863532879 290.425700450937 258.282400313066 743.737184763543 341.052781838823 400.566683662433 172.040799340957 27.770894609838 294.825880152081 508.065910688872 501.781825099315 666.805068966936 180.069431053691 193.610433603151 1507.002986062071 25.019992006394 81.748007498489 346.028984289...
result:
ok 100 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3848kb
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.433549546129 96.880923053928 530.330085889911 44.011362169331 64.313365366182 7.392893666126 34.567810207462 148.850160742993 350.338135916149 329.225162779821 68.864765108873 32.824383174613 244.695729427385 685.968837711981 141.362747995939 1601.789826722722 6.885591146174 70.671460705627 5.17...
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3780kb
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.479657002631 977.209322820569 94.486325059361 307.006514588860 1245.629559700636 532.000000000000 369.048777263928 19.554024317232 1509.000000000000 275.094267211330 4242.193351514708 465.656251408812 3478.304242060182 1754.356007200363 1804.466927585933 21.353142660627 415.415534624568 1526.4344...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3776kb
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.574886489291 999.689277678129 6231.529667746115 550.947886095035 182.544124658607 5374.296791209060 825.725781096661 1653.207429169171 2777.109648537486 166.653023806102 1747.004579272762 651.111357603290 242.210006732268 34.266895846222 286.790864568591 2405.246628920582 2133.342213523184 1310.9...
result:
ok 100 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 3860kb
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.643316977093 41.436698710201 39.206555615734 11.180339887499 49.729267036625 26.925824035673 50.931326312987 10.294055820165 117.885537705013 8.602325267043 48.466483264211 21.095023109729 24.038404810405 16.000000000000 48.548944375753 26.061756859551 39.539832078341 10.770329614269 20.973213749...
result:
ok 100 numbers
Test #11:
score: 0
Accepted
time: 1ms
memory: 3772kb
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.517548582156 2119.674780139698 1638.601494195409 144.699689011414 1706.299211744529 2671.668018298681 1442.324859385014 2909.931270666027 5311.386353862803 7894.844203655953 2950.721437208196 1405.197279587167 8052.785977535973 436.084854128185 1910.190147123788 1597.007827156774 8923.079345158...
result:
ok 100 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 3860kb
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.003943812648 344430.708764477051 597464.947160122218 57512.000021251275 180112.504983949446 254594.189465463656 13301.834367631003 246235.741341503861 17086.953736696309 168329.001188149385 580568.278437601170 120047.475965045189 24722.575937794183 252882.798719090410 366.882341145774 108187.7...
result:
ok 100 numbers
Test #13:
score: 0
Accepted
time: 1ms
memory: 3852kb
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.523773639155 126504.999518608820 57518.293697333065 318943.663702541671 169769.250005668786 1497.133893067276 23459.324991965092 853.347816095316 28.351411845908 7526.106524036478 36705.816569039845 575.015321675171 4025.084882225025 31458.023666467034 316549.014556987677 52928.370889344405 13639...
result:
ok 100 numbers
Test #14:
score: 0
Accepted
time: 1ms
memory: 3840kb
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.584562910677 404181.388824374240 311311.528917577991 271785.624537060445 319158.191839094099 77725.025543495052 103690.241569289938 33781.004277552202 16708.608350188832 262422.768227149092 176381.843093329750 159818.483940375299 451836.634220813692 291664.040180887852 406095.266612404608 5914...
result:
ok 100 numbers