Beehive UVALive - 7528

说明转载至：http://blog.csdn.net/clz19960630/article/details/50975965

上面的做法有点缺陷，应该是题目没有相应的数据。

题目地址：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=695&page=show_PRoblem&problem=5550

题目大意： 如图所示，在一个平面上，六边形按图中所示方式排列，问任意两个格子之间需要走多少步才能到达。（经过一个格子算一步）

如果格子0算作第0圈，可以看到每一圈的个数都在有规律的增加。奇数圈+2，偶数圈+4。

根据这个规律先计算出每个点所在的圈数，以及所在圈数的第一个点，中间点，和最后的点。

然后我们来计算每个点的坐标。

以1为坐标原点开始。

设格子1坐标为（0，0），横着的一个格算1，竖着的通过横边向上的算2，斜边的算1。对于输入的一个号码n，通过以下方式获取该格子的坐标。

第一步 首先查找当前格子所处圈数time，first，mid，last分别是当前圈的最左边，中间，最右边的格子。获取当前格子与mid的数字差d=|n-mid|

step1 计算横坐标x。 易知mid在1的正上方，即横坐标为0，由图可以看出mid两侧逐渐斜着向两侧拓展，没拓展一格横坐标向外加一。又因为每一圈向左右两侧最远伸展为time，所以|x|=min（d,time）,然后判断一下x的正负就可以了。

step2 计算纵坐标y。 由图形可以发现，格子是由两侧到中间逐渐升高的，所以只需知道升高了多少就行了。获取一下该格子到两侧的最小距离y0=min（a-first,last-a）。此外，偶数圈会比奇数圈多出半个格子高的起始点，所以起始高度yb=n%2。  由这个图可以看出，当n>3后，每一圈会有dn个格子是垂直上升的，其中dn=min(（n-1）/2,y0); 所以y=yb+2*dn+y0-dn;

最后一步，计算两个格子间距  获取两个格子的坐标p1,p2后，计算一下横纵坐标差，由对称性可以直接取绝对值dx=abs(p1.x-p2.x),dy=abs(p1.y-p2.y) 如果dx=0，或者dy=0，或者两个格子在同一斜排(dx=dy)，直接算即可dis=max(dx,dy)。 可以看出来，任意不在一排的两个点都是可以看做一个平行四边形的对角顶点，而最近的走法就是在整个平行四边形内部走，而且，只要是在内部，不走回头路的话，走的距离都是一样的。 所以，综上对于dx>=dy的情况，距离dis=dx 对于dy>dx的情况，dis=dx+（dy-dx）/2

#include <bits/stdc++.h>using namespace std;const int MAXN=1e4+7;const int inf=1e9;int first[100],num[100],mid[100],last[100];int rn[MAXN];struct point{    int x;    int y;};void get_round(){    int i;    int now=1,time=0,sum=0;    for(i=1;i<=10000;++i)    {        rn[i]=time;        if(sum==0)        {            first[time]=i;            num[time]=now;            mid[time]=now/2+i;            last[time]=mid[time]+now/2;        }        sum++;        if(sum==now)        {            sum=0;            time++;            if(time%2)now+=2;            else now+=4;        }    }}point get_point(int n){    point ans;    int time=rn[n];    int mid_num=mid[time];    ans.x=min(abs(n-mid_num),time);    if(n<mid_num)ans.x*=-1;    int y0=min(n-first[time],last[time]-n);    int dn=min((time)/2,y0);    ans.y=time%2+2*dn+y0-dn;    return ans;}int main(){    int n,m;    get_round();    //for(i=1;i<=30;++i)printf("%d %d %d %d/n",i,rn[i],fp[rn[i]],mid[rn[i]]);    while(~scanf("%d%d",&n,&m))    {        if(!n&&!m)break;        point p1=get_point(n);        point p2=get_point(m);        int dx=abs(p1.x-p2.x);        int dy=abs(p1.y-p2.y);        int ans;        if(dx>=dy)ans=max(dx,dy);        else ans=dx+(dy-dx)/2;        printf("%d/n",ans);    }    return 0;}