Acwing_98_资讯

Acwing_98

创始人

2024-03-22 14:42:20

0次

题目链接

考察知识点： 坐标变换、递归、分治。

核心问题：计算出点的坐标。

策略是递归算出子图形中的坐标，再进行平移得到当前图形中的坐标。

采用下图方式建立坐标系：原点在中心。

在这里插入图片描述

前置知识：

(x,y)(x,y)(x,y) 逆时针旋转 θ\thetaθ 角度，坐标为 (xcos⁡θ−ysin⁡θ,xsin⁡θ−ycos⁡θ)(x\cos\theta-y\sin\theta,x\sin\theta-y\cos\theta)(xcosθ−ysinθ,xsinθ−ycosθ) 。

设 nnn 为等级，mmm 为在等级为 nnn 时的编号。

单位长度=2n单位长度=2^{n}单位长度=2n 。

len=单位长度2=2n−1len = \frac{单位长度}{2} = 2^{n-1}len=2单位长度=2n−1 。

m=4n=22nm=4^{n}=2^{2n}m=4n=22n 。

等级 222 的 000 号图形是由等级 111 的图形顺时针旋转 90°90°90° ，再进行 yyy 轴轴对称得到。

假设在等级 111 中的坐标为 (x,y)(x,y)(x,y) ，旋转后为 (y,−x)(y,-x)(y,−x) ，再进行关于 yyy 轴的轴对称得到 (−y,−x)(-y,-x)(−y,−x) 。

同理可以得到如下表格：

原始坐标	图形0中坐标	图形1中坐标	图形2中坐标	图形3中坐标
(x,y)(x,y)(x,y)	(−y,−x)(-y,-x)(−y,−x)	(x,y)(x,y)(x,y)	(x,y)(x,y)(x,y)	(y,x)(y,x)(y,x)

因为等级 111 的原点和等级 222 的原点不重合，所以需要将原点进行平移。

原点平移后得到最终坐标如下：

原始坐标	图形0	图形1	图形2	图形3
$(x,y) $	(−y−len,−x+len)(-y-len,-x+len)(−y−len,−x+len)	(x+len,y+len)(x+len,y+len)(x+len,y+len)	(x+len,y−len)(x+len,y-len)(x+len,y−len)	(y−len,x−len)(y-len,x-len)(y−len,x−len)

我们的编号从 000 开始，计算坐标注意减一。

时间复杂度： O(n)O(n)O(n)

代码

// #pragma GCC optimize(3)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
// #include 
// #include 
#define endl '\n'
#define x first
#define y second
#define fi first
#define se second
#define PI acos(-1)
// #define PI 3.1415926
#define LL long long
#define INF 0x3f3f3f3f
#define lowbit(x) (-x&x)
#define ULL unsigned LL
#define PLL pair
#define PIL pair
#define PII pair
#define all(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof a)
#define rev(x) reverse(x.begin(), x.end())
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)using namespace std;LL n, a, b;PLL calc(LL n, LL m) {if (n == 0) return {0, 0};LL len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);PLL pos = calc(n - 1, m % cnt);LL x = pos.x, y = pos.y;int z = m / cnt;if (z == 0) {return {-y - len, -x + len};} else if (z == 1) {return {x + len, y + len};} else if (z == 2) {return {x + len, y - len};} return {y - len, x - len};
}void solve() {int tt;cin >> tt;while (tt -- ) {cin >> n >> a >> b;PLL ac = calc(n, a - 1), bc = calc(n, b - 1);double dx = ac.x - bc.x, dy = ac.y - bc.y;    	printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 5);}
}int main() {IOS;solve();return 0;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：【Linux】yum的介绍和使用

下一篇：《爱在 ZStack Cube 超融合》三部曲

Acwing_98

代码

相关内容

热门资讯