Submission #1164732

#TimeUsernameProblemLanguageResultExecution timeMemory
1164732KaleemRazaSyedWish (LMIO19_noras)C++20
38 / 100
1093 ms9812 KiB
#include<bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

int n;
ll r;


int main()
{
  cin >> n >> r;

  ll a[n], b[n], c[n], d[n];
  for(int i = 0; i < n; i ++)
    cin >> a[i] >> b[i] >> c[i] >> d[i];

  vector<pair<ll, ll> > lr;

  for(int i = 0; i < n; i ++)
    {
      pair<ll,ll> res;

      ll mi = 1e9, mx = -1;
      for(ll t = 0; t <= 10000; t++)
	{
	  ll nx = a[i] + (c[i] - a[i]) * t;
	  ll ny = b[i] + (d[i] - b[i]) * t;
	  ll d = nx * nx + ny * ny;
	  if(d <= r * r)
	    mi = min(t, mi), mx = max(mx, t);
	}
      // cerr << mi << ' ' << mx << endl;
      res = {mi, mx};
      lr.push_back(res);
    }
  
  sort(lr.begin(), lr.end());

  multiset<ll> st;

  int ans = 0;
  int j = -1;
  
  for(auto [l, r] : lr)
    {
      while(j + 1 < lr.size() && lr[j + 1].first <= l)
	st.insert(lr[j + 1].second), j++;
      
      while(st.size() && *st.begin() < l)
	st.erase(st.begin());

      ans = max(ans, (int)(st.size()));
    }

  cout << ans << endl;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...