QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203475 | #2483. Roof Escape | nameless_story# | RE | 0ms | 0kb | C++20 | 2.3kb | 2023-10-06 17:44:48 | 2023-10-06 17:44:49 |
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;
assert(n==8&&m==8);
swap(n,m),swap(s.x,s.y),swap(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;
auto norm=[&](ll &d)
{
if (d>0) d=1;
else d=-1;
};
norm(d.x); norm(d.y);
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);
}
}
// cerr<<ans<<endl;
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: 0
Runtime Error
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