說(shuō)明轉(zhuǎn)載至：http://blog.csdn.net/clz19960630/article/details/50975965

上面的做法有點(diǎn)缺陷，應(yīng)該是題目沒(méi)有相應(yīng)的數(shù)據(jù)。

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

題目大意： 如圖所示，在一個(gè)平面上，六邊形按圖中所示方式排列，問(wèn)任意兩個(gè)格子之間需要走多少步才能到達(dá)。（經(jīng)過(guò)一個(gè)格子算一步）

如果格子0算作第0圈，可以看到每一圈的個(gè)數(shù)都在有規(guī)律的增加。奇數(shù)圈+2，偶數(shù)圈+4。

根據(jù)這個(gè)規(guī)律先計(jì)算出每個(gè)點(diǎn)所在的圈數(shù)，以及所在圈數(shù)的第一個(gè)點(diǎn)，中間點(diǎn)，和最后的點(diǎn)。

然后我們來(lái)計(jì)算每個(gè)點(diǎn)的坐標(biāo)。

以1為坐標(biāo)原點(diǎn)開(kāi)始。

設(shè)格子1坐標(biāo)為（0，0），橫著的一個(gè)格算1，豎著的通過(guò)橫邊向上的算2，斜邊的算1。對(duì)于輸入的一個(gè)號(hào)碼n，通過(guò)以下方式獲取該格子的坐標(biāo)。

第一步 首先查找當(dāng)前格子所處圈數(shù)time，first，mid，last分別是當(dāng)前圈的最左邊，中間，最右邊的格子。獲取當(dāng)前格子與mid的數(shù)字差d=|n-mid|

step1 計(jì)算橫坐標(biāo)x。 易知mid在1的正上方，即橫坐標(biāo)為0，由圖可以看出mid兩側(cè)逐漸斜著向兩側(cè)拓展，沒(méi)拓展一格橫坐標(biāo)向外加一。又因?yàn)槊恳蝗ο蜃笥覂蓚?cè)最遠(yuǎn)伸展為time，所以|x|=min（d,time）,然后判斷一下x的正負(fù)就可以了。

step2 計(jì)算縱坐標(biāo)y。 由圖形可以發(fā)現(xiàn)，格子是由兩側(cè)到中間逐漸升高的，所以只需知道升高了多少就行了。獲取一下該格子到兩側(cè)的最小距離y0=min（a-first,last-a）。此外，偶數(shù)圈會(huì)比奇數(shù)圈多出半個(gè)格子高的起始點(diǎn)，所以起始高度yb=n%2。  由這個(gè)圖可以看出，當(dāng)n>3后，每一圈會(huì)有dn個(gè)格子是垂直上升的，其中dn=min(（n-1）/2,y0); 所以y=yb+2*dn+y0-dn;

最后一步，計(jì)算兩個(gè)格子間距  獲取兩個(gè)格子的坐標(biāo)p1,p2后，計(jì)算一下橫縱坐標(biāo)差，由對(duì)稱性可以直接取絕對(duì)值dx=abs(p1.x-p2.x),dy=abs(p1.y-p2.y) 如果dx=0，或者dy=0，或者兩個(gè)格子在同一斜排(dx=dy)，直接算即可dis=max(dx,dy)。 可以看出來(lái)，任意不在一排的兩個(gè)點(diǎn)都是可以看做一個(gè)平行四邊形的對(duì)角頂點(diǎn)，而最近的走法就是在整個(gè)平行四邊形內(nèi)部走，而且，只要是在內(nèi)部，不走回頭路的話，走的距離都是一樣的。 所以，綜上對(duì)于dx>=dy的情況，距離dis=dx 對(duì)于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;}