记录编号	24601	评测结果	AAAAAAAAAA
题目名称	拯救奶牛贝希	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2011-04-12 17:39:57	内存使用	0.37 MiB

#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("rescuea.in","r",stdin);
	freopen("rescuea.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;
}


/*具体分析：
贝希(bx,by)，目标(x,y)
始终保持目标在贝希的上面，即，bx>=x
是同一行的直接左右移动
  abs(y1-y2)+1
先向左下走再朝右下走
	若目标的y是偶数y-1<=by<=y+(bx-x)*2+1
	向左下走(ceil((y+(bx-x)*2+1)/2)-ceil(by/2))*2
        若by是偶数(bx-x-(ceil((y+(bx-x)*2+1)/2)-ceil(by/2)))*2+1
        若by是奇数(bx-x-(ceil((y+(bx-x)*2+1)/2)-ceil(by/2)))*2+2         
        若目标的y是奇数y<=by<=y+(bx-x)*2
	向左下走(ceil((y+(bx-x)*2)/2)-ceil(by/2))*2
		若by是偶数(bx-x-(ceil((y+(bx-x)*2)/2)-ceil(by/2)))*2
		若by是奇数(bx-x-(ceil((y+(bx-x)*2)/2)-ceil(by/2)))*2+1
    先左下，再左走
        目标的y是偶数by<y-1
			左下：(bx-x)*2
            左走：y-by+1
        目标的y是奇数by<y
            左下：(bx-x)*2-1
            左走：y-by+2
    先右下，再右走
        目标的y是偶数y+(bx-x)*2+1<by
            右下：(bx-x)*2
            右走：by-(y+(bx-x)*2)+1
        目标的y是奇数y+(bx-x)*2<by
            右下：(bx-x)*2-1
            右走：by-(y+(bx-x)*2-1)+1
*/