QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203475#2483. Roof Escapenameless_story#RE 0ms0kbC++202.3kb2023-10-06 17:44:482023-10-06 17:44:49

Judging History

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

  • [2023-10-06 17:44:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-06 17:44:48]
  • 提交

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

output:


result: