P4518 [JSOI2018] 绝地反击

· · 题解

P4518 [JSOI2018] 绝地反击

二分答案，将每艘飞船的可达范围与攻击轨道求交，可得一段圆弧。

考虑正 n 边形辐角最小顶点的辐角 \alpha，\alpha \in [0, \frac {2\pi} n)。考虑第 i 艘飞船对应的弧，可知有 \mathcal{O}(1) 段 \alpha 的取值使得弧上有 k 个顶点，另有 \mathcal{O}(1) 段 \alpha 的取值使得弧上有 k + 1 个顶点。取出每艘飞船的分割点，可将 [0, \frac {2\pi} n) 划分为 \mathcal{O}(n) 段，\alpha 取每小段时飞船覆盖顶点的情况不变。

据此，我们将问题转化为：n 个左部点，每个左部点连向一段环区间的右部点，检查是否有完美匹配。直接 Dinic 的复杂度为 \mathcal{O}(n ^ 3\sqrt n\log V)，不知道是否可以通过。但网络流有两个性质没用到，一是连边为环区间，二是只需检查是否有完美匹配，不用求最大匹配。

自然，考虑霍尔定理 \forall S, |N(S)| \geq |S|。笔者一开始有以下思路：

两种思路本质上为从霍尔定理直接下手直接证明存在性，行不通。考虑不存在性，即 \exists S, |N(S)| < |S|。

从 S\to N(S) 的角度上文已经试过行不通，考虑 N(S)\to S。枚举一段环子区间右部点 N(S)，考虑覆盖集合包含于这些右部点的所有左部点 S_{\max}，我们希望 |S_{\max}| 尽量大，大于 N(S)，即可证明不存在。

为什么一定是一段环子区间？考虑两段 端点不相邻 的不交子区间 [a, b] 与 [c, d]，如果 N([a, b] \cup [c, d]) 不合法，必然有 N([a, b]) 或 N([c, d]) 不合法。

证明：因 [a, b] 与 [c, d] 端点不相邻且不交，所以覆盖集合包含于 [a, b] 的左部点 S_{a, b} 与覆盖集合包含于 [c, d] 的左部点 S_{c, d} 不交，再根据覆盖集合为环区间可知 S_{\max} = S_{a, b} + S_{c, d}，结合 |S_{\max}| > (b - a + 1) + (d - c + 1)，故 |S_{a, b}| > b - a + 1 或 |S_{c, d}| > d - c + 1。

为什么从存在性角度入手不行？因为存在的条件是 任意均满足，而不存在的条件是 存在不满足，后者一般比前者更容易检查。同时满足性无法拆分，即若 |S_{\max}| \leq (b - a + 1) + (d - c + 1) 无法说明 |S_{a, b}| \leq b - a + 1 且 |S_{c, d}| \leq d - c + 1，故无法通过仅检查子区间实现判定。

综上，只需检查是否存在右部点环子区间满足覆盖区间完全包含于该子区间的左部点数量大于该子区间。若是，则无解，否则有解。破环成链，最朴素暴力 \mathcal{O}(n ^ 4\log V)，扫描线可以做到 \mathcal{O}(n ^ 3\log V)，加入线段树优化后可以做到 \mathcal{O}(n ^ 2\log n\log V)，相当优秀。我就知道这题有 \tilde{O}(n ^ 2) 的做法！

此外，还有一种使得只需进行 \mathcal{O}(n\log V) 次检查的方法：顶点必然取到某段弧的左边界或右边界，调整易证。这样更好写。

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 400 + 5;
constexpr double eps = 1e-10;
constexpr double pi = acos(-1);
int n, x[N], y[N], sq[N], R;
double arc, dist[N], arg[N], l[N], r[N];
int val[N << 2], laz[N << 2];
void clear() {
  memset(val, 0, sizeof(val));
  memset(laz, 0, sizeof(laz));
}
void tag(int x, int v) {val[x] += v, laz[x] += v;}
void down(int x) {
  if(laz[x]) {
    tag(x << 1, laz[x]), tag(x << 1 | 1, laz[x]);
    laz[x] = 0;
  }
}
void modify(int l, int r, int ql, int qr, int x, int v) {
  if(ql <= l && r <= qr) return tag(x, v), void();
  int m = l + r >> 1;
  down(x);
  if(ql <= m) modify(l, m, ql, qr, x << 1, v);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
  val[x] = max(val[x << 1], val[x << 1 | 1]);
}
int query(int l, int r, int ql, int qr, int x) {
  if(ql <= l && r <= qr) return val[x];
  int m = l + r >> 1, ans = -N;
  down(x);
  if(ql <= m) ans = query(l, m, ql, qr, x << 1);
  if(m < qr) ans = max(ans, query(m + 1, r, ql, qr, x << 1 | 1));
  return ans;
}
vector<int> buc[N];
bool legal(double a) {
  assert(a >= 0);
  a -= (int) (a / arc) * arc;
  clear();
  int m = n * 2;
  for(int i = 0; i < m; i++) buc[i].clear();
  for(int i = 1; i <= n; i++) {
    double x = l[i] - eps, y = r[i] + eps;
    int pl = x < a ? 0 : (int) ((x - a) / arc) + 1;
    int pr = y < a ? -1 : (int) ((y - a) / arc);
    if(pl > pr) return 0;
    buc[pr].push_back(pl);
    if(pr < n) buc[pr + n].push_back(pl + n);
  }
  for(int i = 0; i < m; i++) {
    for(int it : buc[i]) modify(0, m, 0, it, 1, 1);
    modify(0, m, 0, i, 1, -1);
    if(query(0, m, i - n + 1, i, 1) > 0) return 0;
  }
  return 1;
}
bool check(double d) {
  for(int i = 1; i <= n; i++)
    if(dist[i] + R - eps <= d) l[i] = 0, r[i] = 2 * pi - arc;
    else {
      double a = acos((R * R + sq[i] - d * d) / 2.0 / R / dist[i]);
      l[i] = ::arg[i] - a, r[i] = ::arg[i] + a;
      if(l[i] < 0) l[i] += 2 * pi, r[i] += 2 * pi;
    }
  for(int i = 1; i <= n; i++) {
    if(legal(l[i]) || legal(r[i])) return 1;
  }
  return 0;
}
bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  cin >> n >> R, arc = 2 * pi / n;
  double l = 0, r = sqrt(2.0) * 200;
  for(int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
    dist[i] = sqrt(sq[i] = x[i] * x[i] + y[i] * y[i]);
    ::arg[i] = atan2(y[i], x[i]);
    if(::arg[i] < 0) ::arg[i] += 2 * pi;
    l = max(l, fabs(dist[i] - R) + eps);
  }
  for(int _ = 1; _ <= 30; _++) {
    double m = (l + r) * 0.5;
    if(check(m)) r = m;
    else l = m;
  }
  printf("%.7lf\n", l);
  return cerr << "Time: " << clock() << "\n", 0;
}
/*
2022/7/7
start thinking at ?:??
首先二分答案转化为判定性问题。
但是每艘飞船可能覆盖 k 或 k + 1 个点。
分界线只有 O(n) 个，可以分别考虑所有区间。
那问题就转化成环上 n 个区间，每个区间选一个点，使得一个区间恰好对应一个点，即有完美匹配。
感觉可以用霍尔定理检查，好像不行。
现在已经有 O(n log V) 次检查了，常数还挺大。
如果 n <= 50 可以直接跑二分图匹配。可惜跑不得。
submit.
哇，真能霍尔定理啊！
哇，soft O(n ^ 2)！
start coding at 11:15
finish debugging at 13:16
*/