Submission #626610

#	Time	Username	Problem	Language	Result	Execution time	Memory
626610		mkisic	Wish (LMIO19_noras)	C++14	100 / 100	503 ms	11352 KiB

noras

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

#define X first
#define Y second

typedef long long ll;
typedef pair<long long, long long> pii;

const int MAXN = 2e5 + 5;
const ll INF = (1LL << 60) + 5;
const ll INF_binary = (1 << 30);

int n;
ll R;
vector<pii> dogadaji;

double udaljenost(pii T) { return sqrt((double)T.X * T.X + (double)T.Y * T.Y); }

pii izracunaj_tocku(ll x, ll y, ll sx, ll sy, ll t) {
  ll x2 = min(INF, x + t * sx);
  ll y2 = min(INF, y + t * sy);
  // cerr << x2 << ' ' << y2 << '\n';
  return {x2, y2};
}

void dodaj_tocku() {
  ll x, y, sx, sy;
  cin >> x >> y >> sx >> sy;

  sx -= x;
  sy -= y;

  // cerr << '\n' << x << ' ' << y << " : " << sx << ' ' << sy << '\n';

  ll l = 0, r = INF_binary, m1, m2;

  while (r - l >= 3) {
    m1 = l + (r - l) / 3;
    m2 = r - (r - l) / 3;

    double d1 = udaljenost(izracunaj_tocku(x, y, sx, sy, m1));
    double d2 = udaljenost(izracunaj_tocku(x, y, sx, sy, m2));

    // cerr << l << ' ' << r << " : " << m1 << ' ' << m2 << " : " << d1 << ' '
    // << d2 << '\n';

    if (d1 < d2)
      r = m2;
    else
      l = m1;
  }

  for (int i = l + 1; i <= r; i++) {
    if (udaljenost(izracunaj_tocku(x, y, sx, sy, l)) >
        udaljenost(izracunaj_tocku(x, y, sx, sy, i)))
      l = i;
  }

  pii sredina = izracunaj_tocku(x, y, sx, sy, l);
  ll xx = sredina.X;
  ll yy = sredina.Y;

  // cerr << "sredina " << l << " : " << xx << ' ' << yy;
  // cerr << " : " << udaljenost({xx, yy}) << ' ' << r << '\n';

  if (udaljenost({xx, yy}) > R)
    return;

  ll lo = 0, hi = l, mid;

  while (lo < hi) {
    mid = (lo + hi) / 2;

    double d = udaljenost(izracunaj_tocku(x, y, sx, sy, mid));

    // cerr << lo << ' ' << hi << " : " << mid << ' ' << d << ' ' << R << '\n';

    if (d <= R)
      hi = mid;
    else
      lo = mid + 1;
  }

  ll t1 = lo;

  lo = l, hi = INF_binary;

  while (lo < hi) {
    mid = (lo + hi) / 2 + 1;

    double d = udaljenost(izracunaj_tocku(x, y, sx, sy, mid));

    if (d <= R)
      lo = mid;
    else
      hi = mid - 1;
  }

  ll t2 = lo;

  // cerr << t1 << ' ' << t2 << '\n';

  dogadaji.push_back({t1 * 2, +1});
  dogadaji.push_back({t2 * 2 + 1, -1});
}

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

  cin >> n >> R;

  for (int i = 0; i < n; i++) {
    dodaj_tocku();
  }

  int maks = 0;
  int trenutno = 0;

  sort(dogadaji.begin(), dogadaji.end());

  // cerr << '\n';

  for (auto nx : dogadaji) {
    trenutno += nx.Y;
    maks = max(maks, trenutno);
  }

  cout << maks << '\n';

  return 0;
}

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