QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#654957 | #7670. Messenger | sz051 | WA | 297ms | 129988kb | C++20 | 2.8kb | 2024-10-18 23:16:05 | 2024-10-18 23:16:05 |
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,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);
mn=min(mn,getd(cura-curb,cura+sa[posa]*(db[posb]-t-lsta)-curb-sb[posb]*(db[posb]-lstb)));
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]);
mn=min(mn,getd(cura-curb,cura+sa[posa]*(da[posa]-lsta)-curb-sb[posb]*(da[posa]+t-lstb)));
cura=cura+sa[posa]*(da[posa]-lsta);
curb=curb+sb[posb]*(da[posa]+t-lstb);
lsta=da[posa];
lstb=da[posa]+t;
posa++;
}
}
return mn<=t;
}
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;
//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: 23ms
memory: 128492kb
input:
2 0 0 0 10 2 4 10 4 0
output:
4.000000000
result:
ok correct
Test #2:
score: 0
Accepted
time: 28ms
memory: 126964kb
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: 15ms
memory: 126892kb
input:
2 0 30000 0 0 2 0 0 30000 0
output:
impossible
result:
ok correct
Test #4:
score: 0
Accepted
time: 16ms
memory: 127972kb
input:
2 0 30000 0 0 2 30000 0 0 0
output:
0.000000000
result:
ok correct
Test #5:
score: 0
Accepted
time: 23ms
memory: 127908kb
input:
2 30000 0 0 0 2 30000 30000 0 30000
output:
impossible
result:
ok correct
Test #6:
score: 0
Accepted
time: 16ms
memory: 128684kb
input:
2 30000 0 0 0 2 0 30000 30000 30000
output:
29999.999999999
result:
ok correct
Test #7:
score: -100
Wrong Answer
time: 297ms
memory: 129988kb
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.400000000
result:
wrong answer read 3.400000000000 but expected 3.313708498985