\(\text{Problem}\)

给出向量 \(\boldsymbol a = (x1,y1), \boldsymbol b = (x2,y2)\)

求 \(|\lambda_1\boldsymbol a + \lambda_2\boldsymbol b|\) 的最小值

其中 \(\lambda_1,\lambda_2\) 为整数

\(\text{Solution}\)

二维欧几里得算法的应用

然而并不懂是什么东西，我们只考虑这道题

做法见金斌的集训队论文《欧几里得算法的应用》

Here

注意共线的向量答案为 \(0\) 要特判

\(\text{Code}\)

#include <cstdio>

#include <cmath>

#include <iostream>

#define IN inline

using namespace std;

struct Vector{double x, y;}a, b;

IN double operator * (const Vector &a, const Vector &b){return a.x * b.x + a.y * b.y;}

IN Vector operator * (const Vector &a, double k){return Vector{a.x * k, a.y * k};}

IN Vector operator + (const Vector &a, const Vector &b){return Vector{a.x + b.x, a.y + b.y};}

IN Vector operator - (const Vector &a, const Vector &b){return Vector{a.x - b.x, a.y - b.y};}

IN double cos(Vector a, Vector b){return a * b / (sqrt(a * a) * sqrt(b * b));}

int main()

{

	freopen("math.in", "r", stdin), freopen("math.out", "w", stdout);

	while (~scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y))

	{

		if (a * a > b * b) swap(a, b);

		if (a * b < 0) b = b * -1;

		double cos_alpha = cos(a, b);

		if (cos_alpha >= 1){printf("0\n"); continue;}

		while (cos_alpha > 0.5)

		{

			Vector c = b * cos_alpha;

			if (c * c < a * a) b = b - a;

			else b = b - a * (int)(sqrt(c * c) / sqrt(a * a));

			if (a * a > b * b) swap(a, b);

			if (a * b < 0) b = b * -1;

			cos_alpha = cos(a, b);

		}

		printf("%.0lf\n", min(a * a, b * b));

	}

}

巴特西

JZOJ 3736. 【NOI2014模拟7.11】数学题

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章