题目
有一个无限大的蜂巢迷宫,为了方便表示每一个六边形格子,现在把座标引入到这个迷宫中,如上图年示。
艾瑞特在这个迷宫中街,刚开始他在(0,0)的位置,按照下图所示的路线在这个迷宫中行走。
走了n步以后,他想知道自己在哪个位置了。
思路
走1-6步1层,7-18步2层,二分查找层数,在最后一层6个if走6边
代码
c++ #include<bits/stdc++.h> #define ll long long #define db double using namespace std; ll n; int main(){ cin>>n; if(n==0){ cout<<"0 0\n"; return 0; } ll l=1,r=1e9,mid,lev; while(l<=r){ mid=(l+r)>>1; if(3*mid*(mid-1)<n){ l=mid+1; lev=mid; } else r=mid-1; } //cout<<lev<<endl; ll cx=-1+2*lev,cy=2; n-=3*lev*(lev-1);n--; if(n<=lev-1){ cx-=n,cy+=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=(lev-1); cx-=(lev-1),cy+=2*(lev-1); if(n<=lev){ cx-=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx-=lev*2; if(n<=lev){ cx-=n,cy-=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx-=lev,cy-=2*lev; if(n<=lev){ cx+=n,cy-=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx+=lev,cy-=2*lev; if(n<=lev){ cx+=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx+=2*lev; if(n<=lev){ cx+=n,cy+=2*n; cout<<cx<<' '<<cy<<endl; return 0; } n-=lev; cx+=lev,cy+=2*lev; return 0; }