QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203012 | #2483. Roof Escape | PlentyOfPenalty# | RE | 2ms | 5980kb | C++20 | 2.1kb | 2023-10-06 14:37:34 | 2023-10-06 14:37:34 |
Judging History
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
*/
详细
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