QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168255 | #2483. Roof Escape | LaStataleBlue# | WA | 1ms | 3784kb | C++23 | 3.0kb | 2023-09-08 01:52:26 | 2023-09-08 01:52:27 |
Judging History
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'