QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121224#6124. King Of ZombiesEastKingWA 1ms3680kbC++172.9kb2023-07-07 19:42:442023-07-07 19:42:45

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:42:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3680kb
  • [2023-07-07 19:42:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int M=1005,inf=1e9;
const double eps=1e-8;
#define fi first
#define se second
int n,D;
int dcmp(double x){
	if(fabs(x)<eps)return 0;
	return x>0?1:-1;
}
struct node{
	double x,y;
	node operator +(const node&tmp)const{
		return (node){x+tmp.x,y+tmp.y};
	}
	node operator -(const node&tmp)const{
		return (node){x-tmp.x,y-tmp.y}; 
	}
	node operator /(const double &a)const{
		return (node){x/a,y/a}; 
	}
	node operator *(const double &a)const{
		return (node){x*a,y*a}; 
	}
	void pt(){
		printf("%f %f\n",x,y);
	}
}A[M],V[M];
double dis[M];
typedef pair<double,int> Pi;
double cross(node a,node b){
	return a.x*b.y-a.y*b.x;
}
double length(node a){
	return sqrt(a.x*a.x+a.y*a.y);
}
double disl(node p,node a,node b){
	node v=p-a;
	node u=b-a;
	return fabs(cross(v,u))/length(u);
}
double dot(node a,node b){
	return a.x*b.x+a.y*b.y;
}
double calc(node a,node b){
	if(dcmp(dot(a,b))<0)return -1;
	if(dcmp(cross(a,b))!=0){
		//printf("assert:\n");
		//printf("%.f %d\n",cross(a,b),dcmp(cross(a,b))==0);
		a.pt();
		b.pt();
		assert(0);
	}
	double tm=length(a)/length(b);
	return tm;
}
node Intersect_line(node a,node b,node c,node d){//两直线交点 
//if(cross(b-a,d-c)==0)return node(inf,inf);//前提 不共线
	double s1=cross(d-c,a-c);
	double s2=cross(d-c,b-c);
	return a+(b-a)*s1/(s1-s2);
}
vector<int>update(int x){
	vector<int>Q;
	for(int y=1;y<=n;y++){
		if(y==x)continue;
		node v=V[x]-V[y];
		node p=A[y];
		node a=A[x];
		node b=a+v;
		//printf("v1:%.10f %.10f\n",v.x,v.y);
		if(dcmp(v.x)==0&&dcmp(v.y)==0){
			//printf("v2:%f %f\n",v.x,v.y);
			if(dcmp(length(a-p)-D)<=0){
				if(dis[y]>dis[x]){
					dis[y]=dis[x];
					Q.push_back(y);
				}
			}
			continue;
		}
		double d=disl(p,a,b);
		if(dcmp(d-D)>0)continue;
		node nl={-v.y,v.x};
		double del=sqrt(D*D-d*d);
		node dir=v/length(v)*del;
		node pot;
		if(dcmp(cross(p-a,v))==0)pot=p;
		else pot=Intersect_line(p,p+nl,a,b);
		//printf("x=%d y=%d\n",x,y);
		double tl=calc(pot+dir-a,v),tr=calc(pot-dir-a,v);
		if(dcmp(tl-tr)>0)swap(tl,tr);
		printf("%lf %lf\n",tl,tr);
		if(dcmp(dis[x]-tr)<=0){
			double val=max(dis[x],tl);
			//printf("%lf\n",val);
			if(dcmp(dis[y]-val)>0){
				dis[y]=val;
				Q.push_back(y);
			}
		}
	}
	return Q;
}
void solve(){
	priority_queue<Pi,vector<Pi>,greater<Pi>>Q;
	Q.push({0,0});
	int cnt=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("%.15f\n",dis[i]);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3680kb

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.626227 4.040440
-1.000000 1.000000
3.292893 4.707107
-1.000000 -1.000000
14.285714 14.285714
-1.000000 -1.000000
3.000000 3.600000
-1.000000 -1.000000
3.000000 3.600000
2.626226552146786
0.000000000000000
3.000000000000000
-1
14.285714285714286

result:

wrong answer 1st numbers differ - expected: '2.6262266', found: '2.6262270', error = '0.0000002'