QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#151146 | #6117. Determine The Fluctuation Bonus | Sommohito# | WA | 0ms | 3748kb | C++20 | 2.7kb | 2023-08-26 15:35:07 | 2023-08-26 15:35:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long 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=200;
while(cnt--)
{
if(low+1e-18>=high) break;
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);
low=after;
ans=1e9;
cnt=500;
while(cnt--)
{
if(low+1e-18>=high) break;
ld mid=(low+high)/2;
pair<ld,ld> posa=getpos(a,mid);
pair<ld,ld> posb=getpos(b,mid);
ld dist=getdist(posa,posb);
if(dist<=D)
{
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;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3748kb
input:
3 7 2 -1 1 4 2 5 3 6 1 -7 3 -6 2 9
output:
-1 -1 0.760354545
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'