QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#654992 | #7670. Messenger | sz051 | WA | 220ms | 130756kb | C++20 | 2.9kb | 2024-10-18 23:38:23 | 2024-10-18 23:38:23 |
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);
}
} 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;
}
}
double mn=4e18;
while(1){
if(posa==n+1 || posb==m+1){
break;
}
if(da[posa]>db[posb]-t){
// printf("[%Lf]",db[posb]-t);
if(getd(cura-curb,cura+sa[posa]*(db[posb]-t-lsta)-curb-sb[posb]*(db[posb]-lstb))<=t){
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[posb]);
if(getd(cura-curb,cura+sa[posa]*(da[posa]-lsta)-curb-sb[posb]*(da[posa]+t-lstb))<=t){
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;
// printf("[%d]",chk(937.5));
double ql=0,qr=db[m];
while(ql<qr-1e-9){
double mid=(ql+qr)/2;
//printf("[%Lf]\n",mid);
if(chk(mid)){
qr=mid;
}else{
ql=mid;
}
}
printf("%.9Lf",ql);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 128588kb
input:
2 0 0 0 10 2 4 10 4 0
output:
4.000000000
result:
ok correct
Test #2:
score: 0
Accepted
time: 17ms
memory: 127048kb
input:
2 0 0 1 0 3 2 0 3 0 3 10
output:
5.000000000
result:
ok correct
Test #3:
score: 0
Accepted
time: 19ms
memory: 126956kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 25ms
memory: 128444kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 26ms
memory: 127900kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 38ms
memory: 128088kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
29999.999999999
result:
ok correct
Test #7:
score: 0
Accepted
time: 220ms
memory: 130756kb
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.313708499
result:
ok correct
Test #8:
score: 0
Accepted
time: 20ms
memory: 127724kb
input:
2 0 0 30000 30000 2 0 30000 30000 0
output:
0.000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 19ms
memory: 128060kb
input:
2 0 30000 0 0 2 1 0 0 0
output:
impossible
result:
ok correct
Test #10:
score: 0
Accepted
time: 31ms
memory: 128256kb
input:
2 0 1 0 0 2 30000 0 0 0
output:
14999.500000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 20ms
memory: 126896kb
input:
2 0 0 15000 0 2 30000 0 15000 0
output:
0.000000000
result:
ok correct
Test #12:
score: 0
Accepted
time: 18ms
memory: 128072kb
input:
2 0 0 14999 0 2 30000 0 15000 0
output:
0.999999999
result:
ok correct
Test #13:
score: 0
Accepted
time: 4ms
memory: 127844kb
input:
2 0 0 15000 0 2 30000 0 15001 0
output:
impossible
result:
ok correct
Test #14:
score: 0
Accepted
time: 11ms
memory: 128328kb
input:
2 0 15000 0 0 2 0 15000 0 30000
output:
0.000000000
result:
ok correct
Test #15:
score: 0
Accepted
time: 18ms
memory: 126628kb
input:
2 0 14999 0 0 2 0 15000 0 30000
output:
impossible
result:
ok correct
Test #16:
score: 0
Accepted
time: 25ms
memory: 128524kb
input:
2 0 0 0 30000 2 0 30000 0 0
output:
0.000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 24ms
memory: 127412kb
input:
2 0 30000 0 15000 2 0 15000 0 0
output:
impossible
result:
ok correct
Test #18:
score: 0
Accepted
time: 28ms
memory: 127356kb
input:
2 0 0 30000 30000 2 1 1 30000 30000
output:
impossible
result:
ok correct
Test #19:
score: -100
Wrong Answer
time: 3ms
memory: 128380kb
input:
3 0 30000 15000 15000 0 0 3 30000 30000 15000 15000 30000 0
output:
166.386285096
result:
wrong answer read 166.386285096000 but expected 0.000000000000