QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203012#2483. Roof EscapePlentyOfPenalty#RE 2ms5980kbC++202.1kb2023-10-06 14:37:342023-10-06 14:37:34

Judging History

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

  • [2023-10-06 14:37:34]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:5980kb
  • [2023-10-06 14:37:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m,sx,sy,ex,ey,vx,vy,g;
int nx,ny,mx,my,mm;
double ans;
vector<int>v[N+10];
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
bool Check(int x,int y){
	//cout<<"CHECK "<<x<<" "<<y<<"\n";
	return 1ll*(x-sx)*abs(vy)<1ll*abs(y-sy)*vx;
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey);
	if(sx>ex)swap(sx,ex),swap(sy,ey);
	vx=ex-sx,vy=ey-sy,g=gcd(abs(vx),abs(vy));
	ans=sqrt(1.0*vx*vx+1.0*vy*vy);
	vx/=g,vy/=g;
	if((vx^vy)&1)vx<<=1,vy<<=1;
	for(int i=1;i<=(n>>1);++i)v[i].resize((m>>1)+1);
	for(int i=1;i<=(m>>1);++i){
		for(int j=1;j<=(n>>1);++j)scanf("%d",&v[j][i]);
	}
	if(!vx){
		if(sy>ey)swap(sy,ey);
		for(int i=sy;i<ey;i+=2)ans+=abs(v[sx+1>>1][i+1>>1]-v[sx+1>>1][i+3>>1]);
		printf("%.10lf",ans);
		return 0;
	}
	if(!vy){
		for(int i=sx;i<ex;i+=2)ans+=abs(v[i+1>>1][sy+1>>1]-v[i+3>>1][sy+1>>1]);
		printf("%.10lf",ans);
		return 0;
	}
	//cout<<"ANS="<<ans<<"\n";
	while(sx!=ex||sy!=ey){
		nx=mx=sx-(sx&1);
		if(vy<0)ny=sy-(sy&1?1:2),my=sy+(sy&1);
		else ny=sy-(sy&1),my=sy+(sy&1?1:2);
		while(mx<sx+vx||(vy>0?(my<sy+vy):(ny>sy+vy))){
			//cout<<"("<<nx<<","<<ny<<") ("<<mx<<","<<my<<")\n";
			//assert(nx>=0&&ny>=0);
			if(nx==mx){
				if(mx>sx)ans+=abs(v[nx>>1][my>>1]-v[nx+2>>1][my>>1]);
				if(Check(nx+2,vy<0?ny:my))nx+=2,mx=nx;
				else mx+=2,(vy<0?my=ny:ny=my);
			}else{
				if(mx>sx)ans+=abs(v[mx>>1][ny>>1]-v[mx>>1][ny+2>>1]);
				if(Check(mx,vy<0?ny-2:ny+2))nx+=2,(vy<0?ny-=2:my+=2);
				else ny+=(vy<0?-2:2),my=ny;
			}
			//cout<<"ANS="<<ans<<"\n";
		}
		//cout<<"("<<sx<<","<<sy<<")->("<<sx+vx<<","<<sy+vy<<") ans="<<ans<<"\n";
		assert(sx>0&&sy>0);
		sx+=vx,sy+=vy;
		if((sx!=ex||sy!=ey)&&(!(sx&1))){
			mm=max(max(v[sx>>1][sy>>1],v[sx+2>>1][sy+2>>1]),max(v[sx+2>>1][sy>>1],v[sx>>1][sy+2>>1]));
			//cout<<"mm="<<mm<<"\n";
			if(vy<0)ans+=(mm<<1)-v[sx>>1][sy+2>>1]-v[sx+2>>1][sy>>1];
			else ans+=(mm<<1)-v[sx>>1][sy>>1]-v[sx+2>>1][sy+2>>1];
		}
		//cout<<"->ans="<<ans<<"\n";
	}
	printf("%.12lf",ans);
	return 0;
}
/*
8 8 1 7 7 1
2 3 2 0
2 1 1 2
1 2 0 0
0 0 0 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5980kb

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.083189157585

result:

ok found '53.08319', expected '53.08319', error '0.00000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5960kb

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.485281374239

result:

ok found '14.48528', expected '14.48528', error '0.00000'

Test #3:

score: -100
Runtime Error

input:

2 2 1 1 1 1
100

output:


result: