ICPC WF 2020, Problem F. Ley Lines

Solution and explanation for Problem F. Ley Lines from the ICPC World Finals 2020, along with the implementation.

There is also a short video editorial from ICPCNews, with Yakov Dlougach explaining the solution.

§ Problem

(Link) You have $n$ ($3 \le n \le 3000$) points and a pencil of thickness $t$. Find the maximum number of points you can cover with a single stroke.

§ Observations

Can always cover two points

You can just draw over the line joining them. So now the non-trivial problem is, are there 3 or more points you can cover?

Incomplete

§ Implementation

First, let us pull out our Point template.

using dbl = long double;
const dbl PI = acos(-1);

const dbl EPS = 1e-18;
inline bool zero(dbl a) { return fabs(a) < EPS; }

template <class T>
struct Point {
  using P = Point<T>;
  T x, y;
  Point(T x, T y) : x(x), y(y) {}
  explicit Point() : x(0), y(0) {}

  bool operator==(const P &p) const { return zero(x - p.x) && zero(y - p.y); }
  P operator-(const P &p) const { return P(x - p.x, y - p.y); }
  P operator+(const P &p) const { return P(x + p.x, y + p.y); }
  P operator*(T s) const { return P(x * s, y * s); }
  P operator/(T s) const { return P(x / s, y / s); }
  T cross(const P &p) const { return x * p.y - y * p.x; }
  T dot(const P &p) const { return x * p.x + y * p.y; }
  T norm2() const { return dot(*this); }
  dbl norm() const { return sqrt(norm2()); }
  dbl angle() const { return atan2(y, x); }
  P rot90() const { return P(-y, x); }
  P unit() const { return P(x / norm(), y / norm()); }
};

using P = Point<dbl>;

Now we need to compute the slopes of the tangents

pair<dbl, dbl> tangents(const P &p, dbl r) {
  const dbl alpha2 = 1 - (r * r) / p.norm2();
  const P v = p.unit() * sqrt(alpha2);
  const P vp = p.unit().rot90() * sqrt(1 - alpha2);
  return {(v - vp).angle(), (v + vp).angle()};
}

Now, the full solution:

// faster to read as ints instead of floats
inline int read() { int v; cin >> v; return v; }

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  const int n = read(); // number of points
  const dbl t = read(); // thickness of the pencil
  vector<P> pts(n); // the points
  for (auto &p : pts) {
    p.x = read();
    p.y = read();
  }

  // the event list, pair of angle and entry/exit flag.
  vector<pair<dbl, bool>> ev;
  auto add_event = [&](dbl s, dbl e) { // enter at angle `s`, exit at `e`.
    while (e < s)
      e += 2 * PI;
    for (dbl off : {0.0l, 2 * PI}) {
      ev.emplace_back(s + off, true);
      ev.emplace_back(e + off, false);
    }
  };

  int ans = 2; // two points always possible
  for (auto p : pts) { // pick the first point on the boundary, as origin.
    ev.clear();
    for (auto q : pts) {
      if (p == q) continue;
      q = q - p; // translate the point
      if (q.norm() <= t) { // case 1
        dbl a = q.angle();
        add_event(a, a + PI);
      } else { // case 2
        auto [a, b] = tangents(q, t);
        auto c = q.angle();
        add_event(c, b);
        add_event(a + PI, c + PI);
      }
    }
    // sort by angle, and for equal angle, prefer entry events
    sort(ev.begin(), ev.end(), [&](auto l, auto r) {
      if (zero(l.fst - r.fst)) return l.snd && !r.snd;
      return l.fst < r.fst;
    });

    // angle sweep to process the rotation of the stroke.
    int cur = 1, best = 1;
    for (const auto &[_, e] : ev) {
      cur += (e ? 1 : -1);
      best = max(best, cur);
    }
    ans = max(ans, best);
  }
  cout << ans << endl;

  return 0;
}

Last updated: 01.09.2023