A – Convert to Ones
压缩之后算有多少个 \(01\) 对，然后找小的代价乘上再加上取反的代价即可。
比较显然，我们需要选两个点集，最后贡献就是两个点集的极差积。排个序，并且把每个长度为 \(n\) 的区间都给做一遍即可。
大概可以想到，先把所有的数除掉一个 GCD 之后再来计算出现次数最多的素因子。我们用埃筛筛一下每个数的最小素因子，然后暴力除做标记即可。
先把曼哈顿距离做答案，然后枚举这两个点初始的方向，然后取个最小值即可。
// CF1078A.cpp
#include <bits/stdc++.h>
using namespace std;
double a, b, c, x[3], y[3];
double calcByX(double x) { return (-1.0 * a * x - c) / b; }
double calcByY(double y) { return (-1.0 * b * y - c) / a; }
int main()
{
scanf("%lf%lf%lf%lf%lf%lf%lf", &a, &b, &c, &x[1], &y[1], &x[2], &y[2]);
double ans = fabs(x[1] - x[2]) + fabs(y[1] - y[2]);
if (a != 0 && b != 0)
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
{
double pos1X, pos1Y, pos2X, pos2Y;
double pans = 0;
if (i == 0)
pos1X = calcByY(y[1]), pos1Y = y[1], pans += fabs(pos1X - x[1]);
else
pos1X = x[1], pos1Y = calcByX(x[1]), pans += fabs(pos1Y - y[1]);
if (j == 0)
pos2X = calcByY(y[2]), pos2Y = y[2], pans += fabs(pos2X - x[2]);
else
pos2X = x[2], pos2Y = calcByX(x[2]), pans += fabs(pos2Y - y[2]);
pans += sqrt((pos1X - pos2X) * (pos1X - pos2X) + (pos1Y - pos2Y) * (pos1Y - pos2Y));
ans = min(ans, pans);
}
printf("%.10lf\n", ans);
return 0;
}