QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532747 | #4145. 拯救小云公主 | WhileTrueRP | 90 | 623ms | 4024kb | C++14 | 1.1kb | 2024-08-25 11:08:12 | 2024-08-25 11:08:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 3e3+5;
const double eps = 1e-5;
int x[N],y[N],f[N];
int n,tx,ty;
double dis(int a,int b){
return sqrtl(1ll * (x[a]-x[b]) * (x[a]-x[b]) + 1ll * (y[a]-y[b]) * (y[a]-y[b]));
}
int get(int t){
return f[t] == t ? t : f[t] = get(f[t]);
}
bool check(double t){
for(int i=0;i<=n+1;i++){
f[i] = i;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(dis(i,j) <= t*2.0){
int xx = get(i);
int yy = get(j);
if(xx != yy){
f[xx] = yy;
}
}
}
}
for(int i=1;i<=n;i++){
if((double)x[i]-1 <= t){
int xx = get(0);
int yy = get(i);
if(xx != yy){
f[xx] = yy;
}
}
if((double)y[i]-1 <= t){
int xx = get(n+1);
int yy = get(i);
if(xx != yy){
f[xx] = yy;
}
}
}
return get(0) != get(n+1);
}
int main(){
scanf("%d%d%d",&n,&tx,&ty);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
double l = 0,r = 1e9;
for(int i=1;i<=50;i++){
double mid = (l+r)/2.0;
if(check(mid)){
l = mid;
}else{
r = mid;
}
}
l += eps;
printf("%.2lf",l);
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 4000kb
input:
10 41 39 3 6 6 13 28 29 4 16 22 24 28 17 15 35 15 8 3 23 29 23
output:
5.00
result:
ok single line: '5.00'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3932kb
input:
10 10 10 3 9 7 1 7 3 2 7 3 8 2 5 7 9 4 7 1 3 1 7
output:
2.00
result:
ok single line: '2.00'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3884kb
input:
100 21111 19999 4072 2438 3636 2126 2922 11226 884 3894 12675 293 19308 10241 6337 13604 346 12468 7786 6399 15309 17533 20325 1552 1416 19960 4 9578 2513 10064 6120 12574 17484 3141 5629 4920 2812 18325 17155 5513 18329 3606 1387 1576 7056 3875 3014 6044 3234 2487 11474 884 5475 4286 13536 2038 256...
output:
852.61
result:
ok single line: '852.61'
Test #4:
score: 0
Wrong Answer
time: 8ms
memory: 3948kb
input:
333 333 29999 44 24299 84 8234 5 6039 23 2747 329 8274 295 12531 154 22045 133 29313 89 1470 214 28400 131 7360 216 24271 34 27579 240 2063 134 24021 36 20908 156 18825 78 14992 109 16039 89 14260 152 109 209 15752 13 17396 189 870 2 14877 73 1073 250 20078 31 22418 116 14695 265 4183 135 26427 309 ...
output:
60.39
result:
wrong answer 1st lines differ - expected: '57.00', found: '60.39'
Test #5:
score: 10
Accepted
time: 69ms
memory: 4020kb
input:
1000 30000 30000 25741 25407 10985 20952 18353 14568 29936 14849 18109 318 26784 17773 12107 24978 26886 28162 27254 1383 682 9788 6297 14583 1390 7040 6744 86 137 29357 10981 25012 6357 13045 28540 1974 8342 21227 8240 5703 14909 7132 11754 13483 1179 22371 2479 23444 12666 1544 28961 13737 22072 1...
output:
408.06
result:
ok single line: '408.06'
Test #6:
score: 10
Accepted
time: 157ms
memory: 3968kb
input:
1500 10000 23333 6515 16875 7722 22326 5307 4366 3923 9213 1964 15018 4498 4879 6141 14297 781 8521 6126 7249 8578 14575 4795 13550 960 7766 7009 9012 1223 1934 17 6608 9453 8949 627 9221 6067 2253 3932 4117 8791 16619 1811 5502 4939 23163 2145 18693 8838 193 3591 21654 8858 3797 6852 1782 9606 3872...
output:
175.76
result:
ok single line: '175.76'
Test #7:
score: 10
Accepted
time: 277ms
memory: 4020kb
input:
2000 23333 17777 3335 12753 5370 6421 8007 15647 5803 2703 21577 3193 17547 12505 8092 5542 5236 4211 8620 3490 5753 6122 4268 2481 5761 337 1888 10042 19685 4851 7601 14434 6658 1559 20025 11159 6848 5542 2249 6765 4629 14905 5601 5471 6226 565 13094 6333 2122 5069 2247 1102 8483 9949 14595 12433 2...
output:
227.86
result:
ok single line: '227.86'
Test #8:
score: 10
Accepted
time: 613ms
memory: 4024kb
input:
3000 30000 30000 26982 13801 16395 22739 5731 2165 252 16597 1057 20580 3348 1742 3504 21126 5764 268 27243 20616 8227 3499 18812 1868 5392 18379 18083 8118 921 1429 7219 5321 2604 16847 13917 7602 28332 9471 2992 27218 18231 29532 24289 25378 2229 827 19912 3106 11779 19657 20908 5138 15264 4836 53...
output:
80.00
result:
ok single line: '80.00'
Test #9:
score: 10
Accepted
time: 380ms
memory: 3980kb
input:
2333 10000 19999 7302 18569 379 1649 752 3769 360 4637 3561 7893 1621 6059 426 4266 7908 5466 1198 4049 3797 15156 3420 8904 2285 17681 7382 10535 4775 7646 3489 4209 1785 3865 2902 4938 9176 10750 7848 4490 8222 9447 8551 13613 8331 8206 1652 15797 3961 214 5382 1548 1781 8972 4028 11680 9595 3911 ...
output:
130.22
result:
ok single line: '130.22'
Test #10:
score: 10
Accepted
time: 623ms
memory: 4000kb
input:
3000 23311 17345 4105 1547 265 11896 1314 12787 20992 3140 1643 4742 16444 7601 8312 8986 8202 9706 22324 13571 22337 1975 6436 9104 3516 1048 3655 4376 16910 9894 2252 12213 5746 9986 8425 3025 3826 12587 14263 11811 4648 367 12292 16434 18520 518 3076 15648 8191 3066 18089 7721 6328 141 6005 12779...
output:
168.50
result:
ok single line: '168.50'