Submission #253199

#	Time	Username	Problem	Language	Result	Execution time	Memory
253199		rama_pang	Wish (LMIO19_noras)	C++14	100 / 100	731 ms	7308 KiB

noras

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const double EPS = 1e-9;

int N, R;

double Evaluate(lint a, lint b, lint c, lint d, double t) {
  lint dx = c - a;
  lint dy = d - b;
  double x = (double) a + dx * t;
  double y = (double) b + dy * t;
  return x * x + y * y - (double(R) * double(R));
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> R;
  vector<pair<lint, lint>> segs;
  for (int i = 0; i < N; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    double lo = 0, hi = 4e8;
    for (int rep = 0; rep < 160; rep++) {
      double md1 = (lo + lo + hi) / 3;
      double md2 = (lo + hi + hi) / 3;
      if (Evaluate(a, b, c, d, md1) < Evaluate(a, b, c, d, md2)) {
        hi = md2;
      } else {
        lo = md1;
      }
    }
    if (Evaluate(a, b, c, d, lo) > 0) {
      continue;
    }
    double piv = lo;
    lint l, r;
    {
      lint lo = 0, hi = ceil(piv);
      while (lo < hi) {
        lint md = (lo + hi) / 2;
        if (Evaluate(a, b, c, d, md) < EPS) {
          hi = md;
        } else {
          lo = md + 1;
        }
      }
      l = lo;
    }
    {
      lint lo = floor(piv), hi = 4e8;
      while (lo < hi) {
        double md = (lo + hi + 1) / 2;
        if (Evaluate(a, b, c, d, md) < EPS) {
          lo = md;
        } else {
          hi = md - 1;
        }
      }
      r = lo;
    }
    if (Evaluate(a, b, c, d, l) < EPS && Evaluate(a, b, c, d, r) < EPS && l <= r) {
      segs.emplace_back(ceil(l), floor(r));
    }
  }

  int ans = 0, cnt = 0;
  sort(begin(segs), end(segs));
  priority_queue<lint, vector<lint>, greater<lint>> pq;
  for (auto i : segs) {
    pq.emplace(i.second);
    cnt++;
    while (!pq.empty() && pq.top() < i.first) {
      pq.pop();
      cnt--;
    }
    ans = max(ans, cnt);
  }
  
  cout << ans << "\n";
  return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 23 / 23
• Subtask 3: 15 / 15
• Subtask 4: 32 / 32
• Subtask 5: 7 / 7