QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#655018 | #7670. Messenger | sz051 | AC ✓ | 220ms | 132080kb | C++20 | 3.0kb | 2024-10-18 23:47:12 | 2024-10-18 23:47:13 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <cmath>
#define int long long
#define double long double
using namespace std;
void read(int &x){
x=0;
int f=1;
char c=getchar();
while(!('0'<=c && c<='9')){
if(c=='-'){
f=-1;
}
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
struct Vector{
double x,y;
Vector(){
x=y=0;
}
Vector(double xx,double yy){
x=xx;
y=yy;
}
friend Vector operator+(Vector a,Vector b){
return Vector(a.x+b.x,a.y+b.y);
}
friend Vector operator-(Vector a,Vector b){
return Vector(a.x-b.x,a.y-b.y);
}
friend Vector operator*(Vector a,double c){
return Vector(a.x*c,a.y*c);
}
friend double operator*(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
}
double length(){
return sqrt(x*x+y*y);
}
void show(){
printf("(%Lf %Lf)",x,y);
}
} pa[1000010],pb[1000010],sa[1000010],sb[1000010];
int n,m;
double da[1000010],db[1000010];
double getd(Vector a,Vector b){
// printf("[%lf %lf]->[%lf %lf]\n",a.x,a.y,b.x,b.y);
Vector ab=a-b,norm=Vector(ab.y,-ab.x);
if(ab.length()<=1e-9){
return a.length();
}
if((a*norm)*(norm*b)<0){
return min(a.length(),b.length());
}else{
return abs((a*b))/(ab.length());
}
}
bool chk(double t){
int posa=1,posb=1;
double lsta=0,lstb=t;
Vector cura=pa[0],curb=pb[0];
for(int i=1;i<=m;i++){
if(db[i]<t){
curb=pb[i];
}else{
curb=curb+sb[i]*(t-db[i-1]);
posb=i;
break;
}
}
while(1){
if(posa==n+1 || posb==m+1){
break;
}
if(da[posa]>db[posb]-t){
// printf("[%Lf]",db[posb]-t);
// cura.show();
// curb.show();
// putchar('\n');
if(getd(cura-curb,cura+sa[posa]*(db[posb]-t-lsta)-curb-sb[posb]*(db[posb]-lstb))<=t+1e-6){
return 1;
}
cura=cura+sa[posa]*(db[posb]-t-lsta);
curb=curb+sb[posb]*(db[posb]-lstb);
lsta=db[posb]-t;
lstb=db[posb];
posb++;
}else{
// printf("[%Lf]",da[posa]);
// cura.show();
// curb.show();
// putchar('\n');
if(getd(cura-curb,cura+sa[posa]*(da[posa]-lsta)-curb-sb[posb]*(da[posa]+t-lstb))<=t+1e-6){
return 1;
}
cura=cura+sa[posa]*(da[posa]-lsta);
curb=curb+sb[posb]*(da[posa]+t-lstb);
lsta=da[posa];
lstb=da[posa]+t;
posa++;
}
}
return 0;
}
signed main(){
read(n);
n--;
for(int i=0;i<=n;i++){
scanf("%Lf %Lf",&pa[i].x,&pa[i].y);
if(i){
sa[i]=(pa[i]-pa[i-1])*(1.0/(pa[i]-pa[i-1]).length());
da[i]=da[i-1]+(pa[i]-pa[i-1]).length();
}
}
read(m);
m--;
da[0]=db[0]=0;
for(int i=0;i<=m;i++){
scanf("%Lf %Lf",&pb[i].x,&pb[i].y);
if(i){
sb[i]=(pb[i]-pb[i-1])*(1.0/(pb[i]-pb[i-1]).length());
db[i]=db[i-1]+(pb[i]-pb[i-1]).length();
}
}
if((pa[0]-pb[m]).length()>db[m]){
printf("impossible");
return 0;
}
da[n+1]=db[m+1]=4e18;
double ql=0,qr=db[m];
while(ql<qr-1e-9){
double mid=(ql+qr)/2;
if(chk(mid)){
qr=mid;
}else{
ql=mid;
}
}
printf("%.9Lf",ql);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 18ms
memory: 126844kb
input:
2 0 0 0 10 2 4 10 4 0
output:
3.999999000
result:
ok correct
Test #2:
score: 0
Accepted
time: 30ms
memory: 128580kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
4.999995000
result:
ok correct
Test #3:
score: 0
Accepted
time: 28ms
memory: 126772kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 25ms
memory: 127912kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 28ms
memory: 128228kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 24ms
memory: 128576kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
29999.999999000
result:
ok correct
Test #7:
score: 0
Accepted
time: 220ms
memory: 131992kb
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.313707913
result:
ok correct
Test #8:
score: 0
Accepted
time: 18ms
memory: 127592kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 22ms
memory: 127856kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 127916kb
input:
2 0 1 0 0 2 30000 0 0 0
output:
14999.499999500
result:
ok correct
Test #11:
score: 0
Accepted
time: 20ms
memory: 128632kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.000000000
result:
ok correct
Test #12:
score: 0
Accepted
time: 33ms
memory: 127884kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
0.999999500
result:
ok correct
Test #13:
score: 0
Accepted
time: 18ms
memory: 127720kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 29ms
memory: 126912kb
input:
2 0 15000 0 0 2 0 15000 0 30000
output:
0.000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 8ms
memory: 126716kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 15ms
memory: 128124kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 23ms
memory: 128560kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 33ms
memory: 126756kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: 0
Accepted
time: 33ms
memory: 126936kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
0.000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 11ms
memory: 127692kb
input:
2 0 0 0 1 3 30000 12426 30000 0 30000 30000
output:
impossible
result:
ok correct
Test #21:
score: 0
Accepted
time: 16ms
memory: 128156kb
input:
2 0 0 0 1 3 30000 12427 30000 0 30000 30000
output:
42424.975010668
result:
ok correct
Test #22:
score: 0
Accepted
time: 19ms
memory: 128500kb
input:
4 0 30000 0 0 1 0 1 30000 4 30000 30000 30000 0 29999 0 29999 30000
output:
29998.999998999
result:
ok correct
Test #23:
score: 0
Accepted
time: 110ms
memory: 130716kb
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.135620316
result:
ok correct
Test #24:
score: 0
Accepted
time: 38ms
memory: 132052kb
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.000000000
result:
ok correct
Test #25:
score: 0
Accepted
time: 16ms
memory: 127820kb
input:
2 1 10 1 11 5 3 8 2 9 10 2 10 3 8 8
output:
1.414212976
result:
ok correct
Test #26:
score: 0
Accepted
time: 24ms
memory: 126952kb
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.973568560
result:
ok correct
Test #27:
score: 0
Accepted
time: 20ms
memory: 127028kb
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.563907569
result:
ok correct
Test #28:
score: 0
Accepted
time: 18ms
memory: 128172kb
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.759486081
result:
ok correct
Test #29:
score: 0
Accepted
time: 26ms
memory: 126888kb
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.010484992
result:
ok correct
Test #30:
score: 0
Accepted
time: 29ms
memory: 128656kb
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.000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 26ms
memory: 128016kb
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.227629879
result:
ok correct
Test #32:
score: 0
Accepted
time: 21ms
memory: 128116kb
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.247968200
result:
ok correct
Test #33:
score: 0
Accepted
time: 40ms
memory: 130328kb
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.000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 12ms
memory: 128652kb
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.014441071
result:
ok correct
Test #35:
score: 0
Accepted
time: 65ms
memory: 132080kb
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.000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 98ms
memory: 130740kb
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.000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 31ms
memory: 129184kb
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.037960590
result:
ok correct
Test #38:
score: 0
Accepted
time: 16ms
memory: 129176kb
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.243106043
result:
ok correct
Test #39:
score: 0
Accepted
time: 19ms
memory: 128936kb
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.911169868
result:
ok correct
Test #40:
score: 0
Accepted
time: 39ms
memory: 128812kb
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.377614903
result:
ok correct
Test #41:
score: 0
Accepted
time: 24ms
memory: 127708kb
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.093311431
result:
ok correct
Test #42:
score: 0
Accepted
time: 28ms
memory: 126716kb
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.860778750
result:
ok correct
Test #43:
score: 0
Accepted
time: 25ms
memory: 128272kb
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.889786407
result:
ok correct
Test #44:
score: 0
Accepted
time: 7ms
memory: 126776kb
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.538670448
result:
ok correct
Test #45:
score: 0
Accepted
time: 204ms
memory: 129868kb
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.415462081
result:
ok correct
Test #46:
score: 0
Accepted
time: 220ms
memory: 130788kb
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.561452599
result:
ok correct