[CF1375I]线性代数

这题是一道ACM题的加强版(ACM那题是 \(2-D\) 的),所以先说一下ACM题的做法

CF Gym 100959 K

题目大意

给定一个二维平面上的 \(n\) 个点为黑点,问你最多染多少个点变为黑点可以形成一个正方形网格。一个 \(K\times K\) 的正方形网格指,有实数 \(a,b,c,d\) 使得 \(\forall i,j\in[0,K)\cap Z\)\((a+ci+dj,b+di-cj)\) 为黑点。 \(n\leq 10^5\)

题解

将限制转化后变为: 选定一对基底 \(\vec{r_1}, \vec{r_2}\) 和一个原点,使得所有黑点可以在这个原点下,被这个基底用整数系数线性组合

平凡的,\(\vec{r_1}=(1,0),\vec{r_2}=(0,1)\) 一定是一个合法解,但是我们还需要加入的黑点最少。仔细思考可以发现,在基底模长最长的情况下,\(K\) 最小

设给定的所有点有 \(\vec{v_i}=(a_i,b_i)\) ,则一个满足条件的基底,当且仅当 \(\forall i\not= j\)\(\vec{v_i}-\vec{v_j}\) 可以被这个基底用整数系数线性组合。由线性代数知识可知,我们只需要满足 \(\forall i\in[1,n-1]\)\(\vec{v_i}-\vec{v_{i+1}}\) 可以被组合出来即可

所以问题转化为了给定 \(n\) 个向量 \(\vec{w_i}\) ,求一个模长最长的基底可以组合出所有 \(\vec{w_i}\)

再由线性代数知识可以得到,如果我们求解出前 \(i\) 个向量的最长合法基底 \(\vec{r_1},\vec{r_2}\) ,那么只要可以求解出 \(\vec{w_{i+1}},\vec{r_1},\vec{r_2}\) 的最长合法基底。而且稍加计算既可发现,若一个基底可以组合出 \((s,t)\) ,那么一定可以组合出 \((t,-s)\) ,所以问题再次化简为求解出 \(\vec{w_{i+1}},\vec{r_1}\) 的最长合法基底

简化一下记号,即求 \(\vec{a},\vec{b}\) 的最长合法基底。首先给出做法如下:

  • 取两者中模长较长的为 \(\vec{a}\) ,较短的为 \(\vec{b}\) ,令 \(\vec{c}\)\(\vec{b}\) 的四个方向向量中的任意一个
  • \(\vec{a}-\vec{c}\) 的模长小于 \(\vec{a}\) 的模长,\(\vec{a}=\vec{a}-\vec{c}\)
  • \(\vec{a}\) 的模长等于 \(0\) ,则 \(b\) 即为所求基底,否则解决这个子问题

现在需要说明的是,按照这个操作,每次一定可以使 \(\vec{a}\) 的模长减小

考虑将 \(\vec{b}\) 旋转后建立平面直角坐标系,令 \(\vec{c}\)\(x,y\) 轴上,假设当前 \(\vec{c}\)\(x\) 正半轴的基底

那么做 \(\vec{c}\) 的垂直平分线,若 \(\vec{a}\) 的垂直平分线的右侧,则 \(\vec{a}-\vec{c}\) 的模长一定小于 \(\vec{a}\) 的模长

发现,四条垂直平分线覆盖了包含原点的一个边长为 \(|\vec{c}|\) 的小正方形外的所有向量,也就是说,我们每次操作可以试 \(\vec{a}\) 的模长变为 \(\leq \frac{|\vec{c}|}{2}\) 。因此,一定可以试 \(\vec{a}\) 的模长减小,且该操作的运行次数为 \(log 10^9\) 级别

当我们求得基底后,得到 \(\forall i\in[2,n]\) 中,\(\vec{a_i}-\vec{a_1}=x_i\vec{r_1}+y_i\vec{r_2}\) ,那么 \(K=max\{maxx_i-minx_i,maxy_i-miny_i\}+1\)

至此,我们就完成了该题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/***************************************************************
File name: CF100959K.cpp
Author: ljfcnyali
Create time: 2020年10月09日 星期五 16时15分40秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define int long long
#define pii pair<int, int>
#define x first
#define y second
typedef long long LL;

const int maxn = 1e5 + 10;
const int INF = 1e9;

int n;
pii a[maxn], b[maxn];

inline pii operator + (pii a, pii b) { return pii(a.x + b.x, a.y + b.y); }
inline pii operator - (pii a, pii b) { return pii(a.x - b.x, a.y - b.y); }
inline int Getlen(pii x) { return x.x * x.x + x.y * x.y; }

inline void Get(pii &a, pii b)
{
for ( int i = 30; i >= 0; -- i )
{
pii t = pii(b.x * (1 << i), b.y * (1 << i));
if ( t.x > INF || t.y > INF || t.x < -INF | t.y < -INF ) continue ;
if ( Getlen(a - t) < Getlen(a) ) a = a - t;
}
}

inline pii Solve(pii a, pii b)
{
if ( Getlen(a) == 0 || Getlen(b) == 0 ) return a + b;
if ( Getlen(a) < Getlen(b) ) swap(a, b);
Get(a, b);
b = pii(-b.x, -b.y); Get(a, b);
b = pii(b.y, -b.x); Get(a, b);
b = pii(-b.x, -b.y); Get(a, b);
return Solve(a, b);
}

signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%lld", &n);
REP(i, 1, n) scanf("%lld%lld", &a[i].x, &a[i].y);
if ( n == 1 ) { puts("0"); return 0; }
REP(i, 1, n - 1) b[i] = a[i + 1] - a[i];
REP(i, 2, n - 1) b[i] = Solve(b[i - 1], b[i]);
int s = b[n - 1].x, t = b[n - 1].y;
REP(i, 2, n) b[i] = a[i] - a[1];
int Minx = 0, Maxx = 0, Miny = 0, Maxy = 0;
if ( !t ) swap(s, t);
REP(i, 2, n)
{
int x1 = (s * b[i].x + t * b[i].y) / (s * s + t * t);
int y1 = (b[i].x - x1 * s) / t;
Minx = min(Minx, x1); Maxx = max(Maxx, x1);
Miny = min(Miny, y1); Maxy = max(Maxy, y1);
}
int ans = max(Maxx - Minx + 1, Maxy - Miny + 1);
cout << ans * ans - n << endl;
return 0;
}

四元数

在接下来的篇幅中,我们用 \(\vec{v}=(a,b,c)\) 表示三维空间内坐标 \((a,b,c)\) 所代表的向量,用 \(p,q\) 表示四元数,形式为 \(p=s+a\mathbf{i}+b\mathbf{j}+c\mathbf{k}\) ,其中 \(s\) 为实部,\(\mathbf{i},\mathbf{j},\mathbf{k}\) 指虚数单位,称为虚部。另外,我们用四元数描述三维坐标内坐标为 \((a,b,c)\) 的点时,通常使用 \(p=a\mathbf{i}+b\mathbf{j}+c\mathbf{k}\) 。因此在某些时候,为了文本更加精简我们使用 \(\vec{v}\) 代指一个三维坐标代表的四元数的虚部。

首先回顾三维向量的点积和叉积:

  • 使用 \(\vec{v}\cdot \vec{w}=a_1a_2+b_1b_2+c_1c_2\) 表示点积,\(\vec{v}^2\) 表示 \(\vec{v}\cdot \vec{v}\) ,与二维向量类似有 \(\vec{v}^2=|\vec{v}|^2\)
  • 使用 \(\vec{v}\times \vec{w}=(b_1c_2-c_1b_2,c_1a_2-a_1c_2,a_1b_2-b_1a_2)\) 表示叉积

因为我们希望三维向量的四元数表示的乘积可以与叉积得到的结果类似,又因为 \(\mathbf{i}^2=\mathbf{j}^2=\mathbf{k}^2=\mathbf i\mathbf j\mathbf k=-1\),再按照叉积类似的定义如 \(\mathbf i\mathbf j=\mathbf k\)\(\mathbf i\mathbf k=-\mathbf j\) 类似的式子,可以得到三维向量的四元数乘积 \[ (a_1\mathbf{i}+b_1\mathbf{j}+c_1\mathbf{k})(a_2\mathbf{i}+b_2\mathbf{j}+c_2\mathbf{k})= -(a_1a_2+b_1b_2+c_1c_2)+(b_1c_2-c_1b_2)\mathbf i+(c_1a_2-a_1c_2)\mathbf j+(a_1b_2-b_1a_2)\mathbf k \] 因此可得 \((x+\vec{v})(y+\vec{w})=xy-\vec{v}\cdot \vec{w}+y\vec{v}+x\vec{w}+\vec{v}\times \vec{w}\),据此,我们定义了四元数的乘法

定义四元数的范数\(||p||=s^2+\vec{v}\cdot \vec{v}\) ,可以理解为四维上坐标到原点距离的平方。另外,可以证明 \(||pq||=||p||||q||\)

定义四元数 \(p=s+\vec v\) 的共轭 \(\hat{p}=s-\vec v\) ,发现 \(p\hat p=s^2+\vec v\cdot\vec v=||p||\) ,所以有 \(p^{-1}=\frac{\hat p}{||p||}\) 。在 \(||p||=1\) 的情况下,我们有 \(p^{-1}=\hat p\)

至此,我们定义了四元数需要用到的基本运算,接下来考虑如何用四元数表示旋转

我们假设使用四元数 \(q=s+t\vec v\) 来描述旋转,四元数 \(p=\vec w\) 表示任意三维坐标

我们由四元数的乘法也满足模长相乘的性质,又旋转不改变向量的模长,所以 \(||q||=1\)

假设使用 \(p'=qpq^{-1}\) 来描述 \(p\) 在应用四元数 \(q\) 表示的旋转后得到的 \(p'\) \[ p'=qpq^{-1}=(s+t\vec v)\vec w(s-t\vec v)=(-t\vec v\cdot\vec w+s\vec w+t\vec v\times \vec w)(s-t\vec v) \] 其实部为:\(s(-t\vec v\cdot\vec w)+t\vec v\cdot(s\vec w+t\vec v\times \vec w)=t^2\vec v\cdot(\vec v\times \vec w)\) ,联系三个三维向量的标量三重积表示这三个三维向量围成的排序六面体的有向面积,因为有两个向量重合,所以面积为0,即实部为0,这证明了我们得到的 \(p'\) 代表一个三维向量

又有: \[ \begin{aligned} p'q=&qp\\ \vec bq=&q\vec a\\ s\vec b+t\vec b\times \vec v-t\vec b\cdot \vec v=&s\vec a+t\vec v\times \vec a-t\vec v\cdot \vec a \end{aligned} \\\Rightarrow \begin{cases} \vec b\cdot \vec v=\vec v\cdot \vec a\\ s\vec b+t\vec b\times \vec v=s\vec a+t\vec v\times \vec a \end{cases} \] 发现第一个等式描述了 \(p,p'\)\(\vec v\) 上的投影相等,即说明了 \(p\) 可以通过旋转得到 \(p'\) ,而第二个等式描述了 \(p\) 旋转的角度。同时,可以发现 \(\vec v\) 即为转轴

接下来给出结论,假设旋转角为 \(\theta\) ,转轴为 \(\vec v\) ,则 \(q=\cos\frac{\theta}{2}+\sin\frac{\theta}{2}\vec v\)。详细证明略去,而感性理解方面可以参考二维复数平面上的做法。

可能有人有疑问,为什么需要四个数来描述三维空间的旋转,这里有一个较为优雅的解释:我们首先需要选定 \(x\) 轴在旋转后所到的位置,也就是找到 \((a,b,c)\) 满足 \(a^2+b^2+c^2=1\) 描述 \(x\) 轴的旋转,此时 \(y-z\) 平面也可以进行二维平面上的旋转,所以还需要选定一个 \(\theta\) 。另外,发现 \(a,b,\theta\) 确定后,\(c\) 的取值只有两种,而这就描述了旋转的方向。当然,此处的 \(\vec v\)\(\theta\) 与前文意义不同

CF1375I

题目大意

给定 \(n\) 个三维向量,你需要找到一组模长最长的正交基底,使得这些向量可以由基底用整数系数描述。

\(\vec{v_i}=(a_i,b_i,c_i)\) ,保证 \(gcd_{i=1}^n(a_i,b_i,c_i)=1\)\(n\leq 10000\)

题解

二维情况下,我们可以用 \(\theta\)\(r\) 描述一组正交基底(分别表示旋转角和基底长度),与用 \(\vec{r_1}\) 来描述 \(x\) 轴旋转后的坐标类似

而三维情况下,我们需要一个四元数 \(q\) 和基底长度 \(r\) 来描述一组正交基底,此时,发现前文二维情况所说的做法不适用于三维