BZOJ5328 [SDOI2018] 物理实验

2018 年 05 月 17 日发布.

Description

平面上有一个直线导轨，和 $n$ 个挡板（线段）。现在你可以在直线导轨上的某个位置放置一个长度为 $L$ 的激光发射器；它会以垂直于导轨的方向（向两边）发射激光。激光打到挡板上时会被吸收。

挡板间不相交，挡板和导轨不相交；挡板所在直线和导轨夹角不超过 $85^\circ$ 。

最大化吸收到激光的挡板总长。（只计算被激光照到的部分；计算这部分的挡板长度而不是激光宽度）

$n\leqslant10^4, L\leqslant2\times10^9$ ，所有坐标绝对值 $\leqslant10^9$ 。

多组数据，数据组数 $T\leqslant100$ ，时限 10s 。

Solution

先进行一波平移旋转把导轨转到 $x$ 轴上去。

然后扫描线就好了。对于一二象限的线段，用一棵平衡树分别维护经过当前扫描的横坐标的所有线段。由于这些线段都经过同一个点，所以显然可以直接比较其高低。扫描线时求出每个区间里离横轴最近的线段的...单位长度（就是 $\sqrt{1+k^2}$ ，表示这条线段上 $\Delta x=1$ 时的线段长）。三四象限的做同样处理即可。

之后 $O(n)$ 在区间上扫一遍即可（因为答案区间显然有一个端点可以卡到某线段端点横坐标）。

总复杂度 $O(n\log n)$ 。

Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <set>

namespace _rqy{
typedef long double R;

const int N = 10050;
const R eps = 1e-8;

inline int readInt() {
  int ans = 0, c, f = 1;
  while (!isdigit(c = getchar()))
    if (c == '-') f *= -1;
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans * f;
}

int n;
R x1[N], y1[N], x2[N], y2[N];
R sx1, sy1, sx2, sy2, L;

inline R absR(R a) { return a < 0 ? -a : a; }

inline void Change(R a, R b, R c, R d, R l, R &x, R &y) {
  x = (a * c + b * d) / l;
  y = (a * d - b * c) / l;
}

inline R sqr(R b) { return b * b; }

struct Seg{
  R l, ly, r, ry;
  int i;
  Seg() {}
  Seg(R l, R ly, R r, R ry, int i) : l(l), ly(ly), r(r), ry(ry), i(i) {}
  R Get(R b) const {
    return ((b - l) * ry + (r - b) * ly) / (r - l);
  }
  friend bool operator<(const Seg &a, const Seg &b) {
    R cx = std::max(a.l, b.l) + 1e-5;
    return absR(a.Get(cx)) < absR(b.Get(cx));
  }
  inline bool getType() const {
    R t = absR(ly) > absR(ry) ? ly : ry;
    return t > 0;
  }
  inline R getA() const {
    return std::sqrt(1 + sqr((ry - ly) / (r - l)));
  }
} A[N];

struct Event{
  R t;
  int op, i;
  Event() {}
  Event(R t, int op, int i) : t(t), op(op), i(i) {}
  inline bool operator<(const Event &a) const {
    return t < a.t - eps;
  }
} e[N * 2];

std::set<Seg> Q1, Q2;

R x[N * 2], a[N * 2];

void main() {
  int T = readInt();
  while (T--) {
    n = readInt();
    for (int i = 0; i < n; ++i) {
      x1[i] = readInt();
      y1[i] = readInt();
      x2[i] = readInt();
      y2[i] = readInt();
    }
    sx1 = readInt();
    sy1 = readInt();
    sx2 = readInt() - sx1;
    sy2 = readInt() - sy1;
    R l = std::sqrt(sqr(sx2) + sqr(sy2));
    L = readInt();
    int m = 0;
    for (int i = 0; i < n; ++i) {
      x1[i] -= sx1;
      y1[i] -= sy1;
      x2[i] -= sx1;
      y2[i] -= sy1;
      Change(sx2, sy2, x1[i], y1[i], l, x1[i], y1[i]);
      Change(sx2, sy2, x2[i], y2[i], l, x2[i], y2[i]);
      if (x1[i] > x2[i]) {
        std::swap(x1[i], x2[i]);
        std::swap(y1[i], y2[i]);
      }
      A[i] = Seg(x1[i], y1[i], x2[i], y2[i], i);
      e[m++] = Event(x1[i], 1, i);
      e[m++] = Event(x2[i], -1, i);
    }
    std::sort(e, e + m);
    Q1.clear();
    Q2.clear();
    int t = 0;
    for (int i = 0; i < m; ++i) {
      if (i == 0 || absR(e[i].t - x[t - 1]) > eps) {
        x[t] = e[i].t;
        if (t > 0) {
          a[t - 1] = .0;
          if (!Q1.empty()) a[t - 1] += Q1.begin()->getA();
          if (!Q2.empty()) a[t - 1] += Q2.begin()->getA();
          /*
#ifdef DEBUG
          printf("%Lf %Lf ", x[t - 1], x[t]);
          if (!Q1.empty()) printf("%d ", Q1.top().i); else printf("N/A ");
          if (!Q2.empty()) printf("%d ", Q2.top().i); else printf("N/A ");
          printf("%Lf\n", a[t - 1]);
#endif
          */
        }
        ++t;
      }
      int j = e[i].i;
      std::set<Seg> &Q = A[j].getType() ? Q1 : Q2;
      if (e[i].op == 1) Q.insert(A[j]);
      else Q.erase(A[j]);
    }
    R ans = .0, s = .0;
    for (int i = 0, j = 0; i < t; ++i) {
      while (j + 1 < t && x[j + 1] < x[i] + L) {
        s += a[j] * (x[j + 1] - x[j]);
        ++j;
      }
      ans = std::max(ans, s + (j == t - 1 ? .0 : a[j]) * (L - x[j] + x[i]));
      s -= a[i] * (x[i + 1] - x[i]);
    }
    s = .0;
    for (int i = t - 1, j = t - 1; i >= 0; --i) {
      while (j - 1 >= 0 && x[j - 1] > x[i] - L) {
        s += a[j - 1] * (x[j] - x[j - 1]);
        --j;
      }
      ans = std::max(ans, s + (j == 0 ? .0 : a[j - 1]) * (L + x[j] - x[i]));
      if (i > 0) s -= a[i - 1] * (x[i] - x[i - 1]);
    }
    printf("%.20lf\n", (double)ans);
  }
}
};

int main() {
  freopen("laser.in", "r", stdin);
  freopen("laser.out", "w", stdout);
  _rqy::main();
  return 0;
}