QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121239#6124. King Of ZombiessolemnteeWA 13ms3716kbC++201.8kb2023-07-07 19:51:472023-07-07 19:51:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 19:51:50]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3716kb
  • [2023-07-07 19:51:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int M=1005,inf=1e9;
const double eps=1e-6;
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: 3712kb

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: 0ms
memory: 3708kb

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: 3716kb

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: 3716kb

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'