QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#616700 | #7670. Messenger | ucup-team1004 | AC ✓ | 604ms | 8392kb | C++17 | 2.1kb | 2024-10-06 10:23:20 | 2024-10-06 10:23:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=5e4+10;
const double eps=1e-9;
using vec=complex<double>;
auto dis(const vec &a){
return hypot(real(a),imag(a));
}
double dot(const vec &a,const vec &b){
return real(a)*real(b)+imag(a)*imag(b);
}
double cross(const vec &a,const vec &b){
return dot(a,b*vec(0,-1));
}
vec unit(const vec &a){
return a/dis(a);
}
int n,m;
vec a[N],b[N];
double sa[N],sb[N];
void input(int &n,vec *a,double *s){
scanf("%d",&n),n--;
for(int i=0,x,y;i<=n;i++){
scanf("%d%d",&x,&y),a[i]=vec(x,y);
}
for(int i=1;i<=n;i++)s[i]=s[i-1]+dis(a[i]-a[i-1]);
}
double calc(const vec &a,const vec &b){
if(dis(a-b)<eps)return dis(a);
if(dot(a-b,-b)<0)return dis(b);
if(dot(b-a,-a)<0)return dis(a);
return abs(cross(a,b))/dis(a-b);
}
bool chk(double mid){
vector<pair<double,vec>>t;
int cur=0;
for(;cur<m&&sb[cur+1]<mid;cur++);
for(int i=cur+1;i<=m;i++){
t.push_back({sb[i]-mid,unit(b[i]-b[i-1])});
}
double las=0;
vec now=b[cur]+unit(b[cur+1]-b[cur])*(mid-sb[cur])-a[0];
// debug(t,now);
for(int i=0,j=0;i<n&&j<t.size();){
// debug(i,j,now,las);
if(sa[i+1]<t[j].first){
vec nex=now+(t[j].second-unit(a[i+1]-a[i]))*(sa[i+1]-las);
if(calc(now,nex)<mid+eps)return 1;
now=nex,las=sa[++i];
}else{
vec nex=now+(t[j].second-unit(a[i+1]-a[i]))*(t[j].first-las);
if(calc(now,nex)<mid+eps)return 1;
now=nex,las=t[j++].first;
}
// debug(i,j,now,las,mid);
}
return 0;
}
int main(){
input(n,a,sa),input(m,b,sb);
debug(ary(a,0,n),ary(sa,0,n));
debug(ary(b,0,m),ary(sb,0,m));
if(dis(b[m]-a[0])>sb[m])puts("impossible"),exit(0);
// chk(sb[m]/2),exit(0);
double l=0,r=sb[m],mid;
for(int T=100;T--;){
mid=(l+r)/2;
if(chk(mid))r=mid;
else l=mid;
}
printf("%.15lf\n",r);
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6092kb
input:
2 0 0 0 10 2 4 10 4 0
output:
3.999999999000001
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
4.999999995000002
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.000000000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
29999.999999999003194
result:
ok correct
Test #7:
score: 0
Accepted
time: 366ms
memory: 8388kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
3.313708498398859
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.000000000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
2 0 1 0 0 2 30000 0 0 0
output:
14999.499999999501597
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.000000000000000
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
0.999999999499778
result:
ok correct
Test #13:
score: 0
Accepted
time: 1ms
memory: 5896kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 0 15000 0 0 2 0 15000 0 30000
output:
0.000000000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.000000000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
0.000000000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
2 0 0 0 1 3 30000 12426 30000 0 30000 30000
output:
impossible
result:
ok correct
Test #21:
score: 0
Accepted
time: 0ms
memory: 5952kb
input:
2 0 0 0 1 3 30000 12427 30000 0 30000 30000
output:
42424.975014078852837
result:
ok correct
Test #22:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
4 0 30000 0 0 1 0 1 30000 4 30000 30000 30000 0 29999 0 29999 30000
output:
29998.999999999003194
result:
ok correct
Test #23:
score: 0
Accepted
time: 99ms
memory: 7936kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
24142.135623496935295
result:
ok correct
Test #24:
score: 0
Accepted
time: 63ms
memory: 8232kb
input:
50000 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 ...
output:
0.000000000000000
result:
ok correct
Test #25:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
2 1 10 1 11 5 3 8 2 9 10 2 10 3 8 8
output:
1.414213561787309
result:
ok correct
Test #26:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
3 5 0 0 6 3 6 9 0 2 6 8 6 5 2 5 2 2 9 4 5 0 7 0 8 10
output:
1.973569096884441
result:
ok correct
Test #27:
score: 0
Accepted
time: 0ms
memory: 4048kb
input:
8 4487 25213 15925 2555 11834 19731 24882 25400 29873 18185 20332 1130 20912 4660 2260 17776 7 1181 9778 6861 17903 1110 10850 8648 15950 13243 28850 23075 19352 14768 3464
output:
1452.563908229836215
result:
ok correct
Test #28:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
8 5171 18241 3918 24817 6039 21929 19392 10844 5465 21271 18464 27403 5672 17224 17352 23648 8 13743 27832 6508 18183 93 25279 429 836 959 12741 1631 9065 17093 3127 6232 13449
output:
2339.759487013834132
result:
ok correct
Test #29:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
306 7 0 1 4 9 7 8 6 3 7 2 5 9 2 5 8 6 2 4 9 5 10 10 10 10 3 5 1 3 8 9 6 7 4 8 9 6 4 10 6 6 8 6 3 10 1 0 7 8 5 2 4 1 10 10 10 4 10 10 3 1 10 7 5 1 2 10 8 1 2 3 7 6 1 6 8 5 3 2 8 7 2 0 6 2 5 7 3 0 9 2 9 7 9 8 7 7 1 1 5 7 8 9 3 9 9 0 2 6 7 7 5 5 9 8 4 7 7 8 6 8 0 0 3 0 10 3 6 6 3 1 7 8 5 3 9 7 9 2 7 3 ...
output:
0.010486335574825
result:
ok correct
Test #30:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
283 10 2 8 8 2 9 5 3 6 7 6 2 3 3 10 9 10 4 9 7 3 3 9 6 3 10 3 0 6 10 1 7 8 3 0 5 3 8 10 0 9 4 7 3 3 6 3 2 10 5 6 2 3 6 8 3 10 8 2 6 3 4 2 10 2 8 7 10 0 5 5 0 6 6 2 6 8 9 10 3 6 3 3 9 8 10 0 7 0 10 0 8 1 8 7 1 0 1 7 10 0 1 1 9 8 3 5 10 9 6 7 5 9 8 5 8 8 6 3 5 9 1 9 8 6 1 6 0 0 0 8 1 1 10 2 0 5 0 3 1 ...
output:
0.000000000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 2ms
memory: 3980kb
input:
99 246 227 1374 887 973 515 505 835 445 502 1524 361 589 217 728 637 988 74 1312 1493 192 485 150 951 903 1575 1358 1114 1564 829 262 1465 922 1078 679 912 561 947 1321 1165 948 1333 684 1456 243 1470 654 1373 894 897 149 1089 424 1162 213 293 845 555 508 441 999 1549 406 1020 16 1437 1335 112 174 1...
output:
18.227631720762194
result:
ok correct
Test #32:
score: 0
Accepted
time: 4ms
memory: 4136kb
input:
625 189 776 733 112 1550 794 1148 1341 1236 403 944 153 1152 459 1271 831 203 358 912 1530 1196 1401 1014 758 378 736 130 182 555 20 1425 200 587 755 606 666 1423 1451 624 423 110 1403 26 424 1437 956 796 961 602 1586 331 373 850 800 1559 1508 536 1494 3 598 906 551 1162 1231 1348 106 592 1255 694 1...
output:
4.247969169628051
result:
ok correct
Test #33:
score: 0
Accepted
time: 113ms
memory: 5432kb
input:
18051 32 15 3 3 11 2 2 30 32 14 15 25 34 16 10 12 13 31 14 16 15 35 16 24 18 35 24 4 11 22 21 7 24 12 6 32 25 24 23 2 21 2 3 15 13 9 32 6 26 25 21 30 20 23 22 5 16 11 26 15 15 27 25 32 31 28 5 19 15 20 1 25 3 24 30 5 29 11 19 11 26 9 9 29 7 1 15 3 35 32 18 4 13 25 23 25 32 11 10 19 25 0 28 6 5 35 13...
output:
0.000000000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 23ms
memory: 4244kb
input:
1587 1 16 34 21 28 4 16 22 35 8 1 15 20 18 10 15 23 16 1 23 16 14 15 22 3 34 4 35 34 22 32 16 19 20 7 10 13 20 16 8 11 26 24 35 25 26 19 14 21 4 10 11 3 30 15 11 21 12 11 0 25 17 1 0 33 31 2 26 14 21 19 1 0 32 19 19 3 5 30 29 5 18 21 29 28 8 34 2 25 22 14 5 32 7 1 21 13 23 8 35 31 26 9 2 2 24 25 23 ...
output:
0.014441577291166
result:
ok correct
Test #35:
score: 0
Accepted
time: 226ms
memory: 8136kb
input:
50000 13 5 18 3 8 23 18 33 27 15 14 27 19 22 32 10 18 32 4 35 19 3 17 12 15 33 7 6 30 19 29 8 23 26 1 16 28 25 19 31 21 9 32 11 8 30 7 16 18 18 11 12 30 9 21 35 4 35 2 5 16 21 24 25 10 7 35 24 21 10 5 30 8 0 22 15 19 0 0 33 29 8 31 6 25 29 22 16 22 24 28 25 22 13 28 22 0 29 27 11 0 12 0 1 24 22 19 1...
output:
0.000000000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 461ms
memory: 8208kb
input:
50000 19 16 34 16 26 17 19 6 30 25 11 13 23 13 26 30 22 5 29 19 0 33 29 15 32 23 7 34 28 27 29 23 34 31 33 14 26 10 23 34 21 35 16 0 0 26 2 2 9 25 2 4 17 9 8 1 4 27 7 5 28 14 24 3 24 18 6 22 35 33 10 0 30 20 8 7 11 12 14 21 8 14 1 14 27 24 5 29 2 14 10 19 20 24 13 31 28 32 18 19 29 14 22 34 34 5 1 2...
output:
0.000000001252374
result:
ok correct
Test #37:
score: 0
Accepted
time: 114ms
memory: 7168kb
input:
4 5 5 5 2 4 5 7 6 50000 30 27 31 3 22 30 38 31 39 13 29 33 41 28 21 5 50 26 29 6 42 17 37 12 41 29 35 11 38 30 39 9 45 0 32 7 44 31 40 0 44 30 31 11 31 24 37 4 42 15 23 16 35 28 23 27 25 27 30 35 25 25 44 29 39 12 42 32 44 27 22 22 47 34 22 8 23 14 32 6 39 12 32 25 34 21 29 4 41 35 28 3 40 9 43 19 4...
output:
22.037961466590762
result:
ok correct
Test #38:
score: 0
Accepted
time: 101ms
memory: 8080kb
input:
9 4 10 4 1 8 6 7 4 0 5 4 9 10 1 1 2 1 4 50000 48 7 40 0 42 29 22 13 46 19 35 21 40 19 54 15 55 26 36 21 44 16 31 30 20 5 37 31 51 9 45 31 26 15 54 30 51 1 54 2 54 22 31 2 52 19 43 17 26 31 41 20 38 20 39 19 44 34 52 1 33 29 33 11 38 28 30 29 43 20 52 8 36 29 26 20 45 23 39 13 53 5 47 10 52 3 54 7 40...
output:
20.243106612185986
result:
ok correct
Test #39:
score: 0
Accepted
time: 95ms
memory: 6576kb
input:
2 4 19317 4 19318 37985 41 27 37 16 47 27 31 15 36 13 24 20 49 25 51 23 49 1 33 16 27 16 53 29 43 17 40 9 20 21 24 3 21 19 44 10 36 20 55 15 30 30 35 32 33 26 26 5 35 29 47 27 50 20 33 31 33 3 34 8 35 20 32 23 34 30 26 17 29 10 36 34 21 25 54 29 40 7 38 17 39 9 46 20 35 30 31 33 20 8 32 30 33 26 37 ...
output:
19289.911170620365738
result:
ok correct
Test #40:
score: 0
Accepted
time: 108ms
memory: 6656kb
input:
6 3 25333 0 26159 6 15490 0 3432 4 8641 0 15506 41088 40 9 24 34 30 18 25 25 44 10 55 12 24 14 25 1 21 21 28 16 33 26 42 32 31 34 41 20 50 25 46 4 27 4 23 29 48 8 39 18 54 3 38 14 31 30 55 24 41 2 31 16 45 18 40 32 24 31 39 31 31 2 39 2 26 29 37 22 53 11 29 21 31 31 47 7 35 18 33 4 29 4 28 27 49 14 ...
output:
3406.377615495521695
result:
ok correct
Test #41:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
4 7 18240 5 26771 3 24943 0 6628 7 20 1906 27 15217 20 15532 21 11073 27 334 23 16131 23 18367
output:
3222.093311930320397
result:
ok correct
Test #42:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
4 8 15367 9 13231 10 3412 5 16414 10 26 15046 22 22728 24 22149 20 7329 27 26701 22 4714 27 4268 27 13007 28 27715 20 13727
output:
13.860779749486392
result:
ok correct
Test #43:
score: 0
Accepted
time: 0ms
memory: 4124kb
input:
8 15009 21979 15010 23864 15007 5225 15003 4757 15009 16970 15007 15279 15003 4170 15007 27635 864 14373 15544 14972 14279 14674 14827 14729 14520 15657 15248 14953 14950 14346 14312 14476 14874 14476 15320 15384 15757 15017 15028 14567 14633 15610 14904 14751 15493 14357 14490 15321 14795 14676 151...
output:
17.889788278349197
result:
ok correct
Test #44:
score: 0
Accepted
time: 1ms
memory: 4076kb
input:
6 15005 29323 15004 1778 15008 23555 15000 19170 15010 25875 15010 15988 154 15757 14866 15689 15407 14776 15688 15444 15769 15627 14793 14834 15211 14211 14961 14905 15228 14634 14324 15317 14937 15402 15641 15290 14306 14925 14641 14936 14261 15472 14801 15124 15800 14660 15632 15311 15017 15074 1...
output:
0.538671367585948
result:
ok correct
Test #45:
score: 0
Accepted
time: 510ms
memory: 8392kb
input:
50000 30 20 9 34 25 8 24 4 35 34 6 29 9 15 25 7 4 1 26 21 8 5 31 33 11 28 16 23 29 10 1 30 15 23 14 4 19 22 7 27 11 9 20 12 11 23 30 16 29 24 15 3 5 19 3 2 27 18 25 23 9 2 2 22 18 25 34 35 31 0 35 10 26 28 33 13 28 0 30 33 18 28 0 19 7 25 31 23 26 6 31 33 4 33 5 12 25 15 2 18 22 19 19 5 13 24 13 6 1...
output:
42332.415462585660862
result:
ok correct
Test #46:
score: 0
Accepted
time: 604ms
memory: 8056kb
input:
50000 31 13 2 25 10 20 1 31 9 33 9 28 0 32 30 20 18 15 30 34 10 20 6 1 34 14 26 21 19 18 20 27 11 34 12 18 29 32 8 26 34 10 12 16 15 35 33 30 23 19 26 7 32 12 6 10 27 33 14 11 23 8 6 7 15 10 1 32 16 17 31 26 8 8 11 23 10 34 6 15 7 29 2 16 6 35 17 14 5 8 28 2 6 12 32 7 30 27 6 23 15 27 20 30 17 2 31 ...
output:
42333.561453132489987
result:
ok correct