QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203075 | #2483. Roof Escape | nameless_story# | WA | 0ms | 4044kb | C++20 | 2.2kb | 2023-10-06 15:15:13 | 2023-10-06 15:15:14 |
Judging History
answer
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
struct Q
{
ll x,y;
Q operator-(const Q &o) const { return {x-o.x,y-o.y}; }
Q operator+(const Q &o) const { return {x+o.x,y+o.y}; }
ll operator*(const Q &o) const { return x*o.y-y*o.x; }
ll operator&(const Q &o) const { return x*o.x+y*o.y; }
ll len2() const { return x*x+y*y; };
};
struct seg
{
Q a,b;
seg(Q o,Q p)
{
ll s=o.x-p.x;
if (s>0||!s&&o.y>p.y) swap(o,p);
a=o; b=p;
}
};
int sgn(ll x)
{
if (x<0) return -1;
return !!x;
}
bool intersect(const seg &m,const seg &n)
{
auto a=n.b-n.a,b=m.b-m.a;
auto d=n.a-m.a;
if (n.b.x-m.a.x<0||m.b.x-n.a.x<0) return 0;
if (max(n.a.y,n.b.y)-min(m.a.y,m.b.y)<0||max(m.a.y,m.b.y)<min(n.a.y,n.b.y)) return 0;
return sgn(b*d)*sgn((n.b-m.a)*b)>0&&sgn(a*d)*sgn((m.b-n.a)*a)<0;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cout<<fixed<<setprecision(15);
int n,m,i,j;
Q s,t;
cin>>n>>m>>s.x>>s.y>>t.x>>t.y;
if (s.x==t.x&&s.y==t.y)
{
cout<<0<<endl;
return 0;
}
vector a(n,vector(m,(int)1e9));
for (i=1; i<n; i+=2) for (j=1; j<m; j+=2) cin>>a[i][j];
ll ans=0;
seg l(s,t);
for (i=0; i<=n; i+=2) for (j=0; j<=m; j+=2)
{
{
seg l2(Q{i,j},Q{i,j+2});
if (intersect(l,l2))
{
assert(j<m&&i);
ans+=abs(a[i-1][j+1]-a[i+1][j+1]);
}
}
{
seg l2(Q{i,j},Q{i+2,j});
if (intersect(l,l2))
{
assert(i<n&&j);
ans+=abs(a[i+1][j+1]-a[i+1][j-1]);
}
}
}
ll stl2=(t-s).len2();
Q d=t-s;
if (abs(d.x)==abs(d.y))
{
int gd=gcd(d.x,d.y);
d.x/=gd; d.y/=gd;
}
for (i=0; i<=n; i+=2) for (j=0; j<=m; j+=2)
{
Q o{i,j};
if ((o-s).len2()<stl2&&(o-t).len2()<stl2&&(o-s)*(t-s)==0)
{
assert(i&&j&&i<n&&j<m);
int lst=a[i-d.x][j-d.y];
int cur=a[i+d.x][j+d.y];
vector<int> hh={a[i-1][j-1],a[i-1][j+1],a[i+1][j-1],a[i+1][j+1]};
sort(all(hh));
int mid=max(cur,hh[2]);
ans+=abs(mid-lst)+abs(cur-mid);
}
}
cout<<ans+hypot(s.x-t.x,s.y-t.y)<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3988kb
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.083189157584592
result:
ok found '53.08319', expected '53.08319', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
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.485281374238570
result:
ok found '14.48528', expected '14.48528', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3548kb
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: 3992kb
input:
4 4 1 1 3 3 100 1 1 100
output:
2.828427124746190
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
4 4 1 1 3 3 1 100 100 1
output:
200.828427124746185
result:
ok found '200.82843', expected '200.82843', error '0.00000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
4 4 1 3 3 1 1 100 100 1
output:
2.828427124746190
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3992kb
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.000000000000000
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 28 1 9 1 23 2 1 1 3 2 1 2 0 3 1 1 1 1 3
output:
23.000000000000000
result:
ok found '23.00000', expected '23.00000', error '0.00000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 18 1 11 1 13 1 0 2 0 4 0 2 2 4
output:
4.000000000000000
result:
ok found '4.00000', expected '4.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4000kb
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.000000000000000
result:
ok found '560.00000', expected '560.00000', error '0.00000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3900kb
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.000000000000000
result:
ok found '46.00000', expected '46.00000', error '0.00000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3976kb
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.000000000000000
result:
ok found '49.00000', expected '49.00000', error '0.00000'
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 3924kb
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.000000000000000
result:
wrong answer 1st numbers differ - expected: '30.00000', found: '36.00000', error = '0.20000'