Submission #1164748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164748		KaleemRazaSyed	Wish (LMIO19_noras)	C++20	0 / 100	0 ms	324 KiB

noras

#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;

      if(a[i] - c[i] == 0) // the line is horizontal
	{
	  if(a[i] * a[i] > r * r) continue;
	  ll b2 = r * r - a[i] * a[i];
	  ll b1 = sqrtl(b2);
	  
	  mi = (b1 - b[i]) / (d[i] - b[i]);
	  mx = (-b1 - b[i]) / (d[i] - b[i]);
	  if(mx < mi) swap(mx, mi);
	}
      else if(b[i] - d[i] == 0)
	{
	  if(b[i] * b[i] > r * r) continue;
	  ll b2 = r * r - b[i] * b[i];
	  ll b1 = sqrtl(b2);

	  mi = (b1 - a[i]) / (c[i] - a[i]);
	  mx = (-b1 - a[i]) / (c[i] - a[i]);
	  if(mi > mx) swap(mi, mx);
	}
      else
	{
	  
	}
      if(mx < 0) mi = 0, mx = -1;
      else
	mi = max(mi, 0ll);
      
      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;
}

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