比赛 |
20110412pm |
评测结果 |
EEEEEEEEEE |
题目名称 |
拯救奶牛贝希 |
最终得分 |
0 |
用户昵称 |
kaaala |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-04-12 17:27:13 |
显示代码纯文本
#include<iostream>
#include<cmath>
using namespace std;
struct
{
int step;
int x,y;
}
e[10010];
int n,m;
int bx,by;
void qsort(int l,int r)
{
int i=l,j=r;
int midx=e[(i+j)>>1].x,midy=e[(i+j)>>1].y;
while(i<j)
{
while((e[i].x<midx)||((e[i].x==midx)&&(e[i].y<midy)))
i++;
while((midx<e[j].x)||((midx==e[j].x)&&(midy<e[j].y)))
j--;
if(i<=j)
{
swap(e[i].x,e[j].x);
swap(e[i].y,e[j].y);
i++;
j--;
}
}
if (l<j)
qsort(l,j);
if (i<r)
qsort(i,r);
}
int deal(int x,int y,int bx,int by)
{
int ans=0,ll,rr;
if (x==bx)
{
ans=abs(y-by)+1;
return ans;
}
if(y%2==0)
{
ll=y-1;
rr=y+(bx-x)*2+1;
if(by<ll)
{
ans=(bx-x)*2+y-by+1;
return ans;
}
if(rr<by)
{
ans=(bx-x)*2+by-(y+(bx-x)*2)+1;
return ans;
}
if(ll<=by&&by<=rr)
{
int zx=ceil((rr*1.0)/2.0)-ceil((by*1.0)/2.0);
if(by%2==0)
ans=zx*2+(bx-x-zx)*2+1;
else
ans=zx*2+(bx-x-zx)*2+2;
return ans;
}
}
else
{
ll=y;
rr=y+(bx-x)*2;
if(by<ll)
{
ans=(bx-x)*2-1+y-by+2;
return ans;
}
if(rr<by)
{
ans=(bx-x)*2-1+by-(y+(bx-x)*2-1)+1;
return ans;
}
if(ll<=by&&by<=rr)
{
int zx=ceil((rr*1.0)/2.0)-ceil((by*1.0)/2.0);
if(by%2==0)
ans=zx*2+(bx-x-zx)*2;
else
ans=zx*2+(bx-x-zx)*2+1;
return ans;
}
}
}
int main()
{
int x,y,i;
int k,ans=0x7fffffff;
freopen("rescue.in","r",stdin);
freopen("rescue.out","w",stdout);
scanf("%d%d",&n,&m);
scanf("%d%d",&bx,&by);
for (int i=1;i<=m;i++)
scanf("%d%d",&e[i].x,&e[i].y);
qsort(1,m);
for(i=1;i<=m;i++)
{
x=e[i].x,y=e[i].y;
if(x<=bx)
e[i].step=deal(x,y,bx,by);
else
e[i].step=deal(bx,by,x,y);
}
for(i=1;i<=m;i++)
if(e[i].step<ans)
{
ans=e[i].step;
k=i;
}
printf("%d %d\n%d",e[k].x,e[k].y,ans);
return 0;
}