题解：P11407 [RMI 2020] 寻线 / Nice Lines

· · 题解

考虑一条线怎么做？

首先排除解方程，这样精度爆炸。有两种方法，一种是很自然的把它放到平面直角坐标系中，我们考虑找到它与 x 轴的一个交点，可以利用三分找出，然后再三分找一个交点就可以解出来了。

现在有很多条线，不难发现我们固定一条线，设 f(t) 为 (x_0,t) 查询的答案，它为一堆绝对值函数相加，它是一个凸包。我们希望找出交点，但是交点错综复杂，然而题目保证斜率互不相同且值域很小，我们找一个巨大的 x_0 再找出所有关系就能明确对应关系了。

怎么找呢？考虑分治。考虑对于分治区间 [x,y]，如果 \frac{f(x)+f(y)}{2}=f(\frac{x+y}{2}) 则说明该区间只有一条线，没有交点，直接不管。否则进入 [x,\frac{x+y}{2}]，[\frac{x+y}{2},y] 即可。这样是 \mathcal{O}(n\log V) 的，据说精细实现能过。

考虑优化，发现点数和线段数很少，那么我们考虑找出最左边和最右边的两个线段，分治时求出他们的交点 mid，如果交点在图上，这意味着我们找出了一个点，利用它算出直线并结束分治。否则我们能够找出一条线的信息，那么我们只需优化 3n+2 次操作就能完成。

代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define eb emplace_back
using namespace std;
#define pii pair <ll, ll>
#define inf 1000000000
#define ls (p << 1)
#define rs (ls | 1)
#define id(x, y) ((x - 1) * m + y)
constexpr int N = 1e5, len = 2e4, P = 998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
long double query(long double x, long double y);
void the_lines_are(std::vector<int> a, std::vector<int> b);
class node {
  public:
  ld k, b;
} ;
vector <int> A, B;
node get (ld x) {
  int p = floor (x / N);
  ld d1 (query (N, p * N + len)), d2 (query (N, (p + 1) * N - len));
  ld k ((d1 - d2) / (len * 2 - N));
  return (node) {k, d1 - k * (p * N + len)};
}
void find (node x, node y) {
  if (fabsl (x.k - y.k) < 1e-5) return ;
  ld mid = - (x.b - y.b) / (x.k - y.k);
  ld val = query (N, mid);
  if (fabsl (x.k * mid + x.b - val) < 1e-5 && fabsl (y.k * mid + y.b - val) < 1e-5) {
    ld k = mid / N;
    A.eb (round (k));
    B.eb (round (mid - 1.0 * round (k) * N));
    return ;
  } node Mid = get (mid);
  find (x, Mid), find (y, Mid);
}
void solve (int N, int subtask) {
  find (get (-2e9), get (2e9));
  the_lines_are (A, B);
}