_rqy's Blog

一只猫猫，想成为天才少女数学家！

0%

BZOJ5328 [SDOI2018] 物理实验

发表于 更新于 分类于 阅读次数：

Description

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

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

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

n⩽104,L⩽2×109n\leqslant10^4, L\leqslant2\times10^9 ，所有坐标绝对值 ⩽109\leqslant10^9 。

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

Solution

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

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

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

总复杂度 O(nlog⁡n)O(n\log n) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#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;
}