QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#168260 | #2483. Roof Escape | LaStataleBlue# | WA | 1ms | 3980kb | C++23 | 3.2kb | 2023-09-08 02:22:46 | 2023-09-08 02:22:47 |
Judging History
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(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: 0
Wrong Answer
time: 1ms
memory: 3980kb
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:
wrong answer 1st lines differ - expected: '53.083189157585', found: '53.083189157584590959'