QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121226 | #6124. King Of Zombies | EastKing | RE | 1ms | 3780kb | C++17 | 2.9kb | 2023-07-07 19:43:55 | 2023-07-07 19:43:58 |
Judging History
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: 100
Accepted
time: 1ms
memory: 3660kb
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.626226552146786 0.000000000000000 3.000000000000000 -1 14.285714285714286
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3780kb
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.000000000000000 0.000000000000000 0.000000000000000 -1
result:
ok 4 numbers
Test #3:
score: -100
Dangerous Syscalls
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...