比赛 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;
}