题目大意

给定两个向量，求 $|x\vec{a}+y\vec{b}|$ 最小，$x,y$ 不同时为0。

思路

约定：$|\vec{a}|<|\vec{b}|$ ，且两个向量夹角小于 $\frac{\pi }{2}$

Theorem1 ：两个向量的夹角如果大于等于 $\frac{\pi }{3}$ ，则答案等于 $min(|\vec{a}|,|\vec{b}|)$ 。

Proof：容易得到
$$|x\vec{a}+y\vec{b}{|}^2=|\vec{a}{|}^2{x}^2+|\vec{b}|y^2+2xy|\vec{a}||\vec{b}|cos\theta$$
因为 $\frac{\pi }{3}\le \theta \le \frac{\pi }{2}$ ，所以
$$\begin{gathered} \ge |\vec{a}{|}^2{x}^2+|\vec{b}|y^2+xy|\vec{a}||\vec{b}| \\ \ge |(|\vec{a}|x-|\vec{b}|y{)}^2+xy|\vec{a}||\vec{b}| \end{gathered}$$
当 $x=0,y\ne 0$ 时，$|\vec{b}{|}^2{y}^2\ge |\vec{b}{|}^2\ge |\vec{a}{|}^2$

当 $x\ne 0,y=0$ 时，$|\vec{a}{|}^2{x}^2\ge |\vec{a}{|}^2$

否则 $xy|\vec{a}||\vec{b}|\ge |\vec{a}||\vec{b}|\ge |\vec{a}{|}^2$ 。

所以答案为二者最小值。

Theorem2: $|x\vec{a}+y\vec{b}|=|(x-ky)\vec{a}+y(\vec{b}+k\vec{a})|$

以上证明显然。

发现可以用类似扩欧的做法来做。但如何选择 $k$ 为一大难题。

如图，过点 $B$ 做 $BE\perp OA$ 于 $E$。

我们定义 $\overrightarrow{OA}=\vec{a},\overrightarrow{OB}=\vec{b},\overrightarrow{OC}=\vec{c},\overrightarrow{OD}=\vec{d}$，且 $\vec{c}=k\vec{a},\vec{d}=(k+1)\vec{a}$ ，且点$C,D$ 在 $E$ 点两边。则 $k$ 可以推式子（求 $OE$ 长再除以 $|\vec{a}|$）或二分求得。

容易发现 $\overrightarrow{BC},\vec{a}$ 或 $\overrightarrow{BD},\vec{a}$ 的答案等于 $\vec{a},\vec{b}$ 的答案。其次我们发现 $max(\angle BCD,\angle BDC)>\angle AOB$ 。所以若 $\angle BCD>\angle BDC$ 则选择 $\overrightarrow{BC}$，否则选择 $\overrightarrow{BD}$ 。判断角的大小可以采用大边对大角的方法。

然后就可以递归求解。边界情况即是夹角大于 $\frac{\pi }{3}$ 。

注意：

1. 两个向量共线的情况答案为0
2. 若两个向量的夹角大于 $\frac{\pi }{2}$ ，则可以对任意一个向量关于原点作中心对称。

Code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define sqr(x) (x * x)
#define pi M_PI
#define ll long long
using namespace std;
ll ans;
struct node {ll x, y;ll len() {return x * x + y * y;}node operator + (const node & s) const {return (node){x + s.x, y + s.y};}node operator - (const node & s) const {return (node){x - s.x, y - s.y};}node operator * (const ll & s) const {return (node){x * s, y * s};}ll operator * (const node & s) const {return x * s.x + y * s.y;}
}a, b;
ll work(node a, node b) {if (a.x * b.y - a.y * b.x == 0) return 0;if (a.len() > b.len()) swap(a, b);if (a * b < 0) a.x = -a.x, a.y = -a.y;if (sqr((a * b * 2)) < a.len() * b.len()) return min(a.len(), b.len());ll k = (a * b) / a.len();node c = a * k, d = a * (k + 1);if ((b - c).len() < (b - d).len() && k) return work(b - c, a);else return work(b - d, a);
}
int main() {freopen("math.in", "r", stdin);freopen("math.out", "w", stdout);while (~scanf("%lld%lld%lld%lld", &a.x, &a.y, &b.x, &b.y))printf("%lld\n", work(a, b));fclose(stdin);fclose(stdout);return 0;
}