QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121237 | #6124. King Of Zombies | solemntee | WA | 13ms | 3788kb | C++20 | 1.8kb | 2023-07-07 19:50:37 | 2023-07-07 19:50:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=1005,inf=1e9;
const double eps=1e-7;
int n,D;
double dis[M];
int dcmp(double x){
if(fabs(x)<eps)return 0;
return x>0?1:-1;
}
typedef pair<double,int> Pi;
struct node{
int x,y;
}A[M],V[M];
#define fi first
#define se second
vector<int>update(int x){
vector<int>Q;
for(int i=1;i<=n;i++){
if(i==x)continue;
int x1=A[x].x-A[i].x;
int y1=V[x].x-V[i].x;
int x2=A[x].y-A[i].y;
int y2=V[x].y-V[i].y;
int A1=(y1*y1+y2*y2);
int B1=2*(x1*y1+x2*y2);
int C1=(x1*x1+x2*x2)-D*D;
if(A1==0){
if(C1<=0){
if(dcmp(dis[i]-dis[x])>0){
dis[i]=dis[x];
Q.push_back(i);
}
}
}else{
if(B1*B1<4*A1*C1){
continue;
}else{
double delta=sqrt(1.0*B1*B1-4.0*A1*C1);
double tl=(-B1-delta)/(2.0*A1),tr=(-B1+delta)/(2.0*A1);
if(dcmp(dis[x]-tr)<0){
double val=max(dis[x],tl);
if(dcmp(dis[i]-val)>0){
dis[i]=val;
Q.push_back(i);
}
}
}
}
}
return Q;
}
void solve(){
priority_queue<Pi,vector<Pi>,greater<Pi>>Q;
Q.push({0,0});
while(!Q.empty()){
auto now=Q.top();
Q.pop();
int x=now.se;
if(dcmp(now.fi-dis[x])>0)continue;
vector<int>val=update(x);
for(auto v:val){
Q.push({dis[v],v});
}
}
}
int main(){
scanf("%d %d",&n,&D);
for(int i=1;i<=n;i++)dis[i]=inf;
for(int i=0;i<=n;i++){
int x,y,a,b;
scanf("%d %d",&x,&y);
scanf("%d %d",&a,&b);
A[i]={x,y};
V[i]={a,b};
}
solve();
for(int i=1;i<=n;i++){
if(dis[i]==inf){
printf("-1\n");
}else {
printf("%.10f\n",dis[i]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
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.6262265521 0.0000000000 3.0000000000 -1 14.2857142857
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
4 10 0 0 0 0 10 0 0 0 20 0 0 0 30 0 0 0 41 0 0 0
output:
0.0000000000 0.0000000000 0.0000000000 -1
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 13ms
memory: 3788kb
input:
814 5261 8674 -10000 83 9959 -3135 4963 -5450 -980 -6718 -5021 -5412 1206 8906 -9471 -4357 5471 -3795 2180 -4645 -2664 9110 -5528 9221 -3130 -3916 1465 -6825 5446 1767 -3479 -6871 -7960 -3523 5303 -1141 7806 3362 -3357 7529 -6106 -7323 -8776 3458 3288 -4825 -5940 -4857 95 -3169 6767 -3056 -2340 3228...
output:
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
ok 814 numbers
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3652kb
input:
470 235 5883 -1751 1075 368 7790 2418 3758 -3846 -5164 -3433 -5837 -7492 -3987 -6763 6899 -9252 -7032 2446 -4829 6204 5952 -1391 -6466 -1366 1902 -976 -6563 3105 -726 2931 4726 5388 5891 -2901 -3071 906 1237 6576 -2018 1582 -4444 -974 -537 -7998 -5090 -3067 -6005 -6746 7139 -9713 -6108 5218 150 -569...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9.4843862520 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0.4692992262 -1 -1 -1 -1 -1 0.8519144711 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 8th numbers differ - expected: '3.8776035', found: '-1.0000000', error = '1.2578912'