QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#503324#6831. Known as the Fruit Brotherwangyue2017WA 113ms14164kbC++173.3kb2024-08-03 17:42:052024-08-03 17:42:07

Judging History

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

  • [2024-08-03 17:42:07]
  • 评测
  • 测评结果:WA
  • 用时:113ms
  • 内存:14164kb
  • [2024-08-03 17:42:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define D double
#define P pair<D,D>
#define x first
#define y second
P operator-(const P&a,const P&b){
    return {a.x-b.x,a.y-b.y};
}

P operator+(const P&a,const P&b){
    return {a.x+b.x,a.y+b.y};
}
P operator*(const P&a,const D&b){
    return {a.x*b,a.y*b};
}

D length(const P&a){
    return sqrt(a.x*a.x+a.y*a.y);
}
D dist(const P&a,const P&b){
    return length(a-b);
}
D cross(const P&a,const P&b){
    return a.x*b.y-a.y*b.x;
}
D dot(P a,P b){
    return a.x*b.x+a.y*b.y;
}
const int N =200000;
P d[N];

P barr[50][4];
int n,m,cnt;
D R;
void add_line(P p,P a,P b){
    P v=b-a;
    P pro=a+v*(dot(v,p-a)/dot(v,v));
    if(dist(pro,p)>R)return;
    D res=sqrt(R*R-dist(p,pro)*dist(p,pro));
    d[++cnt]=pro+(b-a)*(1.0/dist(b,a))*res;
    d[++cnt]=pro-(b-a)*(1.0/dist(b,a))*res;
}
void add_point(P d){
    for(int i=1;i<=n;++i){
        for(int j=0;j<=3;++j){
            add_line(d,barr[i][j],barr[i][(j+1)%4]);
        }
    }
}
D  dis[1000][1000];
int sign(D a){
    if(fabs(a<=1e-12))return 0;
    if(a<0)return -1;
    return 1;
}
void clac(int i,int j){
    P a,b;
    a=d[i],b=d[j];
    if(i<=m){
        if(dist(d[i],d[j])<=R+1e-12){
            dis[i][j]=0;
            return;
        }
        else{
            a=a+(b-a)*(1/length(b-a))*R;
            for(int i=1;i<=n;++i){
                if(barr[i][0].first<=a.x&&a.x<=barr[i][2].first&&barr[i][0].y<=a.y&&a.y<=barr[i][2].y){
                    dis[i][j]=1e30;
                    return;
                }
            }
        }
    }
    dis[i][j]=dist(b,a);


    for(int ii=1;ii<=n;++ii){
        for(int jj=0;jj<=3;++jj){
            if(cross(b-a,barr[ii][jj]-a)*(cross(b-a,barr[ii][(jj+2)%4]-a))<0
             &&cross(a-barr[ii][jj],barr[ii][(jj+2)%4]-barr[ii][jj])*cross(b-barr[ii][jj],barr[ii][(jj+2)%4]-barr[ii][jj])<0){
                dis[i][j]=1e30;
                return;
            }
        }
    }
}
D ans[N];
bool in[N];
int pre[N];
int main(){
    cin>>n>>m>>R;
    for(int i=1;i<=n;++i){
        D x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        barr[i][0]={x1,y1};barr[i][1]={x1,y2};barr[i][2]={x2,y2};barr[i][3]={x2,y1};
    }
    for(int i=1;i<=m;++i){
        D x,y;
        cin>>x>>y;
        d[++cnt]={x,y};
    }
    for(int i=1;i<=n;++i){
        for(int j=0;j<=3;++j){
            d[++cnt]=barr[i][j];
        }
    }
    D xs,ys,xt,yt;
    cin>>xs>>ys>>xt>>yt;
    
    d[++cnt]={xs,ys},d[++cnt]={xt,yt};
    int S=cnt-1,T=cnt;
    for(int i=1;i<=m;++i){
        add_point(d[i]);
    }
    for(int i=1;i<=cnt;++i){
        for(int j=1;j<=cnt;++j){
            if(i==j)continue;
            clac(i,j);
        }
    }
    for(int i=1;i<=cnt;++i)ans[i]=1e30;
    priority_queue<pair<double,int>, vector<pair<double,int> >, greater<pair<double,int> > >q;
    ans[S]=0;
    q.push({0,S});
    while(!q.empty()){
        auto [d,u]= q.top(); q.pop();
        if (in[u]) continue; 
        in[u] = 1;
        for (int i = 1; i <= cnt; i++) {
            if (ans[u] + dis[u][i] < ans[i]) {
                ans[i] = ans[u] + dis[u][i];
                pre[i]=u;
                q.push({ans[i], i});
            }
        }
    }
    printf("%.9lf",ans[T]);
    // cout<<ans[T];
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7992kb

input:

1 2 2
0 2 7 4
-3 3
8 2
1 1 6 6

output:

9.543203767

result:

ok found '9.5432038', expected '9.5432038', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7856kb

input:

1 2 3
0 2 7 4
-1 4
8 2
1 1 6 6

output:

7.930391429

result:

ok found '7.9303914', expected '7.9303914', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 8024kb

input:

1 2 2
2 2 7 4
-1 4
8 2
1 1 6 6

output:

7.634413615

result:

ok found '7.6344136', expected '7.6344136', error '0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 9980kb

input:

1 2 1
0 2 7 4
-4 4
8 2
1 1 6 6

output:

9.738768883

result:

ok found '9.7387689', expected '9.7387689', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 7952kb

input:

1 2 2
0 2 7 5
-4 4
8 2
1 1 6 6

output:

9.647559034

result:

ok found '9.6475590', expected '9.6475590', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 8020kb

input:

1 0 114514
0 0 6 2
2 -1 5 3

output:

7.537319188

result:

ok found '7.5373192', expected '7.5373192', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 8024kb

input:

5 4 10
1 -99999 9 99999
11 -99999 19 99999
21 -99999 23 99999
-99999 999999 99999 1000000
-99999 -1000000 99999 -999999
0 0
10 0
20 0
24 7
-1 0 30 7

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 8088kb

input:

5 3 10
1 -99999 9 99999
11 -99999 19 99999
21 -99999 23 99999
-99999 999999 99999 1000000
-99999 -1000000 99999 -999999
0 0
10 0
20 0
-1 0 30 7

output:

3.206555616

result:

ok found '3.2065556', expected '3.2065556', error '0.0000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 8088kb

input:

5 4 1
1 -99999 9 99999
11 -99999 19 99999
21 -99999 23 99999
-99999 999999 99999 1000000
-99999 -1000000 99999 -999999
0 0
10 0
20 0
24 7
-1 0 30 7

output:

200013.000250020

result:

ok found '200013.0002500', expected '200013.0002500', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 9996kb

input:

1 1 6
-999999 2 999999 7
1 1
0 0 8 8

output:

8.485281374

result:

ok found '8.4852814', expected '8.4852814', error '0.0000000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 8004kb

input:

1 1 10
-9999 9 9999 10
0 1
0 0 114 514

output:

516.514034066

result:

ok found '516.5140341', expected '516.5140341', error '0.0000000'

Test #12:

score: -100
Wrong Answer
time: 113ms
memory: 14164kb

input:

29 7 193
19 575 27 714
36 575 44 717
55 575 65 698
75 575 82 755
98 575 105 641
118 575 127 812
168 575 176 888
226 575 234 905
279 575 288 917
287 0 299 496
328 150 335 733
343 153 350 736
360 134 368 717
377 191 383 774
397 77 404 660
415 248 423 831
437 0 444 536
459 324 466 907
491 0 499 548
510...

output:

194.370779697

result:

wrong answer 1st numbers differ - expected: '434.2481536', found: '194.3707797', error = '0.5523970'