POJ 3889 Fractal Streets（逼近模拟）

$ POJ~3889~Fractal~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 intusing 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; }

转载于:https://www.cnblogs.com/812-xiao-wen/p/11248915.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的POJ 3889 Fractal Streets（逼近模拟）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。