QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#151086 | #6124. King Of Zombies | Sommohito# | WA | 1ms | 3700kb | C++20 | 2.7kb | 2023-08-26 15:22:10 | 2023-08-26 15:22:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
const int N=1e3+5;
int n,D;
int x[N],y[N],vx[N],vy[N];
bool done[N];
pair<ld,ld> getpos(int who, ld tm)
{
ld X=x[who]+vx[who]*tm;
ld Y=y[who]+vy[who]*tm;
return make_pair(X,Y);
}
ld getdist(pair<ld,ld> A, pair<ld,ld> B)
{
A.first-=B.first;
A.second-=B.second;
return sqrtl(A.first*A.first+A.second*A.second);
}
ld get(int a,int b,ld after)
{
ld low=after,high=1e9;
ld ans=1e9;
int cnt=400;
while(cnt--)
{
ld mid1=low+(high-low)/3,mid2=high-(high-low)/3;
pair<ld,ld> posa=getpos(a,mid1);
pair<ld,ld> posb=getpos(b,mid1);
ld dist1=getdist(posa,posb);
posa=getpos(a,mid2);
posb=getpos(b,mid2);
ld dist2=getdist(posa,posb);
// debug(dist1,dist2,mid1,mid2);
ans=min({ans,dist1,dist2});
if(dist1<dist2)
{
high=mid2;
}
else
{
low=mid1;
}
}
// debug(ans,low,high);
if(ans>D)
return 1e9;
low=after;
ans=1e9;
cnt=100;
while(cnt--)
{
ld mid=(low+high)/2;
pair<ld,ld> posa=getpos(a,mid);
pair<ld,ld> posb=getpos(b,mid);
ld dist=getdist(posa,posb);
// debug(dist);
if(dist<=D+1e-9)
{
ans=mid;
high=mid;
}
else
low=mid;
}
// debug(a,b,after,ans);
return ans;
}
ld ans[N];
void TEST_CASES()
{
cin>>n>>D;
for(int i=0;i<=n;i++)
cin>>x[i]>>y[i]>>vx[i]>>vy[i];
priority_queue<pair<ld,int>>pq;
pq.push({0.,0});
for(int i=1;i<=n;i++)
ans[i]=1e9;
while(!pq.empty())
{
int z=pq.top().second;
ld tm=-pq.top().first;
pq.pop();
if(done[z])
continue;
done[z]=true;
ans[z]=tm;
for(int i=0;i<=n;i++)
{
if(done[i]) continue;
ld when=get(z,i,tm);
if(when==1e9) continue;
pq.push({-when,i});
}
}
for(int i=1;i<=n;i++)
{
if(ans[i]==1e9) cout<<"-1\n";
else
cout<<fixed<<setprecision(9)<<ans[i]<<"\n";
}
}
/*
*/
int32_t main()
{
#ifndef APURBA
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3700kb
input:
5 3 0 0 3 0 10 10 0 -3 1 1 -1 -1 16 1 -1 0 100 100 100 100 -100 -3 10 0
output:
2.626226552 0.000000000 2.999999999 -1 14.285703220
result:
wrong answer 5th numbers differ - expected: '14.2857143', found: '14.2857032', error = '0.0000008'