POJ 3889 Fractal Streets（逼近模拟）

$ POJFractal~Streets $（模拟）

---

---

$ solution: $

这是一道淳朴的模拟题，最近发现这种题目总是可以用逼近法，就再来练练手吧。

首先对于每个编号我们可以用逼近法求出它在各个图上是处于左上，右上，左下，右下中的哪一个。

inline void bijin(int i,int v){

	if(i==0)return ;

	rg x=1<<(i*2-2),y=1;

	while(v>x)v-=x,++y;

	t[i]=y; bijin(i-1,v);

}

然后我们在用逼近法将它的坐标一步步复原。（中间会涉及旋转操作）

inline void find(int i,int x,int y,int f,su &v){

	if(i>n){v.x=x; v.y=y; return ; }

	rg l=1<<(i-1);

	if(t[i]==1){

		rg xx=x,yy=y;

		x=l-yy+1;

		y=l-xx+1;

	}

	if(t[i]==4){

		rg xx=x,yy=y;

		x=yy;

		y=xx;

	}

	if(t[i]==1||t[i]==2)x+=l;

	if(t[i]==2||t[i]==3)y+=l;

	find(i+1,x,y,t[i],v);

}

---

---

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define rg register int

using namespace std;

int n,a,b;

int t[17];

struct su{

	int x,y;

}sa,sb;

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar()))if(ch=='-')sign=1;

	while(isdigit(ch))res=res*10+(ch^48),ch=getchar();

	if(sign)return -res; else return res;

}

inline void bijin(int i,int v){

	if(i==0)return ;

	rg x=1<<(i*2-2),y=1;

	while(v>x)v-=x,++y;

	t[i]=y; bijin(i-1,v);

}

inline void find(int i,int x,int y,int f,su &v){

	if(i>n){v.x=x; v.y=y; return ; }

	rg l=1<<(i-1);

	if(t[i]==1){

		rg xx=x,yy=y;

		x=l-yy+1;

		y=l-xx+1;

	}

	if(t[i]==4){

		rg xx=x,yy=y;

		x=yy;

		y=xx;

	}

	if(t[i]==1||t[i]==2)x+=l;

	if(t[i]==2||t[i]==3)y+=l;

	find(i+1,x,y,t[i],v);

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	rg tt=qr(); t[0]=1;

	while(tt--){

		n=qr(); a=qr(); b=qr();

		bijin(n,a); find(1,1,1,1,sa);

		bijin(n,b); find(1,1,1,1,sb);

		rg x=sa.x-sb.x,y=sa.y-sb.y;

		db z=sqrt((db)x*x*100+(db)y*y*100);

		rg ans=(int)(z*2)-(int)z;

		printf("%d\n",ans);

	}

	return 0;

}