Fractal-Streets

title: Fractal Streets
date: 2023-12-13 14:48:45
tags: 分形
categories: 算法进阶指南

题目大意

将原来的城市复制一遍放在原城市的上方，将原城市顺时针90°放在原城市的左上方，将逆时针90°后的城市放在原城市的左边，然后用道路将四部分链接起来，反复进行相同操作。

解题思路

这是著名的通过一定规律无限包含自身的“分形”图。为了方便计算，我们把标号从 $0$ 开始
解题关键就是，求编号为 $M$ 的房屋在 $N$ 级城市的位置，把问题转化为 calc(N,M),因此改题目转化为求 $calc(N,A)$ 与 $calc(N,B)$ 的距离。
在求解 $calc(N,M)$ 时，因为 $N?1$ 级城市有 $2^{2?N?2}$ 座房屋，所以我们先求解 $calc(N?1,Mmod{2}^{2?N?2})$,根据房屋编号 M 与 该级数的房屋总数确定编号上下左右位置。
在这里插入图片描述

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1314;

const int MOD = 9901;

typedef pair<LL,LL> PII;

PII calc(LL n,LL m)
{
	if(n == 0) return make_pair(0,0);
	LL len = 1ll << (n - 1),cnt = 1ll << (2 * n - 2);//每一级的半长和多少个 1 级的 
	PII pos = calc(n - 1,m % cnt);
	LL x = pos.first, y = pos.second;
	LL z = m / cnt;
	if(z == 0) return make_pair(y,x);
	else if(z == 1) return make_pair(x,y + len);
	else if(z == 2) return make_pair(x + len,y + len);
	else  return make_pair(2 * len - y - 1,len - x - 1);
}
int main()
{
	int t; cin >> t;
	while(t --)
	{
		LL N,A,B;
		cin >> N >> A >> B;
		PII a = calc(N,A - 1),b = calc(N,B - 1);
		LL x = a.first - b.first, y = a.second - b.second;
		cout << fixed << setprecision(0) << sqrt(x * x + y * y) * 10 << endl; 
	} 
}