QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203075#2483. Roof Escapenameless_story#WA 0ms4044kbC++202.2kb2023-10-06 15:15:132023-10-06 15:15:14

Judging History

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

  • [2023-10-06 15:15:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4044kb
  • [2023-10-06 15:15:13]
  • 提交

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'