A – The Tower is Going Home
发现只有从最左侧出发的横线才可以造成贡献。计算答案的时候，考虑枚举越过的竖线，然后更新答案。
神仙题啊，灵活运用线段树和贪心的好题。首先一个显然的性质：\(X\) 串的 \(\max\) 序列是原串 \(\max\) 序列的前缀串。知道这个之后我们可以开始构造。
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]
大概可以想到，先把所有的数除掉一个 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;
}