《算法竞赛进阶指南》0x02 POJ2889 分形
标签：方便 90度 size clu first iostream stream 根据 竞赛
题目链接：http://poj.org/problem?id=3889
根据对称性以及规律可以分四种情况进行归纳。旋转的情况可以这样考虑，
①、对于位置为(x,y)的点，边长为k的正方形中，顺时针旋转九十度之后的坐标是(y,k-1-x),
②、对于位置(x,y)上的点，边长为k的正方形中，逆时针旋转九十度之后的坐标是(k-1-y,x).
代码如下：
#include
#includeusing namespace std;
typedef long long ll;
int n;
pair calc(int n ,ll m){//计算第n及城市中的编号为m的城市的位置
if(n==1){
if(m==0)return make_pair(0,0);
if(m==1)return make_pair(0,1);
if(m==2)return make_pair(1,1);
if(m==3)return make_pair(1,0);
}
ll len=1ll1),cnt=1ll2*n-2);//cnt为第n-1级城市中的房屋数量,len为其边长
pair pos=calc(n-1,m%cnt);
ll x=pos.first,y=pos.second;
ll z=m/cnt;//确定第n个城市中的m处于哪一个位置
if(z==0)return make_pair(y,x);//右旋90度，垂直翻转
if(z==1)return make_pair(x,y+len);
if(z==2)return make_pair(x+len,y+len);
if(z==3)return make_pair(2*len-y-1,len-x-1);
}
int main(){
int t;
cin>>t;
ll h,o;
while(t--){
scanf("%d %lld %lld",&n,&h,&o);
pair p1=calc(n,h-1);//为了取模方便，将编号减一
pair p2=calc(n,o-1);
ll dx=p1.first-p2.first;
ll dy=p1.second-p2.second;
printf("%.0lf\n",sqrt((double)(dx*dx+dy*dy))*10);
}
}
《算法竞赛进阶指南》0x02 POJ2889 分形
标签：方便 90度 size clu first iostream stream 根据 竞赛
原文地址：https://www.cnblogs.com/randy-lo/p/13124472.html
评论