QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168255#2483. Roof EscapeLaStataleBlue#WA 1ms3784kbC++233.0kb2023-09-08 01:52:262023-09-08 01:52:27

Judging History

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

  • [2023-09-08 01:52:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3784kb
  • [2023-09-08 01:52:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using T = long long; //o double o long double
typedef complex<T> pt;
const T EPS = 1e-10; //per i double o long double
#define X real()
#define Y imag()
#define M_PI acos(-1)
// *** Punti ***
T dot(pt v, pt w) { return (conj(v) * w).X; }
T cross(pt v, pt w) { return (conj(v) * w).Y; }
T orient(pt a, pt b, pt c) { return cross(b-a, c-a); }
pt translate(pt v, pt p) { return p+v; }
pt perp(pt p) { return {-p.Y, p.X}; }
bool isPerp(pt v, pt w) { return dot(v,w) == 0; }
pt scale(pt c, T factor, pt p) { return c+(p-c)*factor; }

bool properInter(pt a, pt b, pt c, pt d, pt &out) {
    T oa = orient(c,d,a), ob = orient(c,d,b),
    oc = orient(a,b,c), od = orient(a,b,d);
    // Proper intersection exists iff opposite signs
    if (oa*ob < 0 && oc*od < 0) {
        out = (a*ob - b*oa) / (ob-oa); // requires floats
        return true;
    }
    return false;
}

bool inDisk(pt a, pt b, pt p) { 
    return dot(a - p, b - p) <= 0;
}
bool onSegment(pt a, pt b, pt p) { 
    return orient(a, b, p) == 0 && inDisk(a, b, p);
}

void solve(int t){
    long long h,w,sx,sy,ex,ey;
    cin>>h>>w>>sx>>sy>>ex>>ey;
    
    pt s(sx,sy),e(ex,ey),tmp;
    
    vector mat(h,vector(w,0ll));
    for(int i=0;i<h/2;i++){
        for(int j=0;j<w/2;j++){
            cin>>mat[i][j];
        }
    }
    
    long double ans=0;
    for(int i=2;i<w;i+=2){
        for(int j=0;j<h;j+=2){
            
            pt p1(j,i),p2(j+2,i);
            
            if(properInter(e,s,p1,p2,tmp)){
                ans+=abs(mat[j/2][i/2-1]-mat[j/2][i/2]);
            }
        }
    }
    
    for(int i=2;i<h;i+=2){
        for(int j=0;j<w;j+=2){
            
            pt p1(i,j),p2(i,j+2);
            
            if(properInter(e,s,p1,p2,tmp)){
                ans+=abs(mat[i/2-1][j/2]-mat[i/2][j/2]);
            }
        }
    }
    
    for(int i=2;i<h;i+=2){
        for(int j=2;j<w;j+=2){
            pt p(i,j);
            
            if(onSegment(s,e,p)){
                long long maxi = -1, maxi2= -1;
                for(long long val : {mat[i/2][j/2],mat[i/2-1][j/2],mat[i/2][j/2-1],mat[i/2-1][j/2-1]}){
                    if(val>maxi){
                        maxi2=maxi;
                        maxi=val;
                    }else if(val>maxi2)maxi2=val;
                }
                
                long long part,dest;
                
                if((sx<i && sy<j) || (ex<i && ey<j)){
                    part = mat[i/2][j/2];
                    dest = mat[i/2-1][j/2-1];
                }else{
                    part = mat[i/2-1][j/2];
                    dest = mat[i/2][j/2-1];
                }
                
                ans+=abs(maxi2-part)+abs(maxi2-dest);
            }
        }
    }
    
    ans+=sqrtl((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey));
    cout<<setprecision(20)<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 26 1 1 3 25
0 1
0 5
5 5
0 1
2 1
4 1
5 0
0 0
1 0
6 4
3 2
5 4
1 5

output:

53.083189157584590959

result:

ok found '53.08319', expected '53.08319', error '0.00000'

Test #2:

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

input:

8 8 1 7 7 1
2 3 2 0
2 1 1 2
1 2 0 0
0 0 0 1

output:

14.485281374238570293

result:

ok found '14.48528', expected '14.48528', error '0.00000'

Test #3:

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

input:

2 2 1 1 1 1
100

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #4:

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

input:

4 4 1 1 3 3
100 1
1 100

output:

2.8284271247461900975

result:

ok found '2.82843', expected '2.82843', error '0.00000'

Test #5:

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

input:

4 4 1 1 3 3
1 100
100 1

output:

200.8284271247461901

result:

ok found '200.82843', expected '200.82843', error '0.00000'

Test #6:

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

input:

4 4 1 3 3 1
1 100
100 1

output:

2.8284271247461900975

result:

ok found '2.82843', expected '2.82843', error '0.00000'

Test #7:

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

input:

2 56 1 23 1 17
1
0
1
0
1
0
0
4
1
3
1
1
3
0
3
1
1
0
0
2
0
2
1
0
1
0
0
0

output:

10

result:

ok found '10.00000', expected '10.00000', error '0.00000'

Test #8:

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

input:

2 28 1 9 1 23
2
1
1
3
2
1
2
0
3
1
1
1
1
3

output:

23

result:

ok found '23.00000', expected '23.00000', error '0.00000'

Test #9:

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

input:

2 18 1 11 1 13
1
0
2
0
4
0
2
2
4

output:

4

result:

ok found '4.00000', expected '4.00000', error '0.00000'

Test #10:

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

input:

2 400 1 133 1 399
3
6
2
3
0
2
0
3
6
1
6
3
1
5
3
1
6
3
0
2
4
3
3
2
3
0
6
4
2
5
0
3
1
1
3
0
1
3
0
3
5
2
1
2
4
5
0
2
1
0
4
7
3
1
6
4
3
5
2
0
0
3
2
0
2
7
1
0
2
1
2
0
3
0
3
0
6
2
0
4
2
0
3
3
5
0
3
6
3
0
3
2
1
5
1
1
2
6
1
2
1
0
1
2
1
3
2
4
0
5
1
4
2
2
4
4
3
2
1
5
2
3
1
0
0
2
7
5
0
0
2
1
1
0
4
4
2
0
1
4
5
...

output:

560

result:

ok found '560.00000', expected '560.00000', error '0.00000'

Test #11:

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

input:

2 200 1 117 1 97
1
7
2
2
0
4
3
0
0
0
0
5
4
0
4
4
7
0
2
7
3
5
0
1
2
4
2
0
0
0
3
3
1
3
2
2
2
0
3
3
3
0
0
3
1
3
4
2
1
6
0
1
0
2
1
3
5
2
5
2
0
1
0
1
0
1
1
3
3
3
1
5
1
1
7
0
2
2
2
7
2
1
4
3
1
1
0
0
1
2
1
0
6
2
2
2
1
1
1
0

output:

46

result:

ok found '46.00000', expected '46.00000', error '0.00000'

Test #12:

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

input:

2 132 1 41 1 65
3
0
3
3
2
2
5
2
0
2
3
3
2
1
2
4
0
4
5
1
2
1
0
2
2
1
0
6
1
1
5
2
1
0
2
4
2
5
1
6
0
3
1
1
5
1
2
7
2
2
2
1
5
6
0
5
4
0
5
2
1
1
1
4
0
0

output:

49

result:

ok found '49.00000', expected '49.00000', error '0.00000'

Test #13:

score: -100
Wrong Answer
time: 0ms
memory: 3720kb

input:

4 100 3 37 3 53
2 0
1 3
0 4
2 0
0 2
0 1
0 4
4 0
5 5
3 6
1 4
1 1
6 0
1 3
3 5
5 4
3 0
2 0
2 3
0 1
0 3
4 4
5 3
3 0
0 2
4 1
0 3
0 5
1 2
1 4
1 0
2 0
2 0
0 0
0 2
4 1
4 0
1 5
4 0
0 2
1 7
6 2
1 4
0 0
0 6
5 5
2 0
0 3
3 1
2 4

output:

36

result:

wrong answer 1st numbers differ - expected: '30.00000', found: '36.00000', error = '0.20000'