QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168266#2483. Roof EscapeLaStataleBlueWA 2ms3884kbC++233.2kb2023-09-08 02:54:492023-09-08 02:54:50

Judging History

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

  • [2023-09-08 02:54:50]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3884kb
  • [2023-09-08 02:54:49]
  • 提交

answer

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

using T = __int128; //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>>w>>h>>sx>>sy>>ex>>ey;
    
    pt s(sx,sy),e(ex,ey),tmp;
    assert(sx%2 && sy%2 && ex%2 && ey%2);
    
    if(s==e){
        cout<<"0\n";
        return;
    }
    
    vector mat(h/2,vector(w/2,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(i,j),p2(i,j+2);
            
            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(j,i),p2(j+2,i);
            
            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(j,i);
            
            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<j && sy<i) || (ex<j && ey<i)){
                    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];
                }
                
                //cout<<p<<" "<<abs(maxi2-part)+abs(maxi2-dest)<<"\n";
                ans+=abs(maxi2-part)+abs(maxi2-dest);
            }
        }
    }
    
    ans+=sqrtl((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey));
    cout<<setprecision(14)<<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: 0ms
memory: 3884kb

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.083189157585

result:

ok single line: '53.083189157585'

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3816kb

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.485281374239

result:

wrong answer 1st lines differ - expected: '14.485281374238', found: '14.485281374239'