poj 1870 Bee Breeding

構想:まず座標を確立し、具体的なやり方はhttp://www.cnblogs.com/xin-hua/p/3237096.htmlを参照してください.
そして、2座標の差x,yが得られる.x,yが同じ番号であれば加算、そうでなければ最大になる.(絶対値をとる)
コードは次のとおりです.
 

 1 #include<iostream>

 2 #include<stdio.h>

 3 #include<algorithm>

 4 #include<iomanip>

 5 #include<cmath>

 6 #include<cstring>

 7 #include<vector>

 8 #define ll __int64

 9 #define pi acos(-1.0)

10 #define MAX 50000

11 using namespace std;

12 struct dir

13 {

14     int x,y;

15     dir(){}

16     dir(int a,int b){

17         x=a;

18         y=b;

19     }

20     dir operator+(dir A){

21         return dir(A.x+x,A.y+y);

22     }

23 }an[6];

24 dir solve(int n)

25 {

26     int k,m,i,j;

27     dir p;

28     k=((sqrt(12.0*n-3.0)-3.0)/6.0);

29     if(3*k*(k+1)+1!=n) k++;

30     p.x=k;p.y=0;

31     m=0;

32     if(k>0) m=6*k-((3*k*(k+1)+1)-n);

33     i=0;

34     while(m){

35         for(j=0;j<k;j++){

36             p=p+an[i];

37             m--;

38             if(m==0)

39                 break;

40         }

41         i++;

42     }

43     return p;

44 }

45 int main(){

46     int n,x,y,ans,m;

47     an[0]=dir(-1,1);an[1]=dir(-1,0);an[2]=dir(0,-1);

48     an[3]=dir(1,-1);an[4]=dir(1,0);an[5]=dir(0,1);

49     while(cin>>n>>m){

50         if(m==0&&n==0) break;

51         dir aa=solve(n);

52         dir bb=solve(m);

53         x=aa.x-bb.x;

54         y=aa.y-bb.y;

55         if((x<0&&y<0)||(x>0&&y>0))

56             ans=abs(x+y);

57         else ans=max(abs(x),abs(y));

58         printf("The distance between cells %d and %d is %d.
",n,m,ans);

59     }

60     return 0;

61 }

View Code