제출 #1164703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164703		KaleemRazaSyed	Wish (LMIO19_noras)	C++20	0 / 100	1 ms	324 KiB

noras

#include<bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

int n;
ll r;

ld TimE(ld y1, ld y2, ld m) {
   return (y2 - y1) / m;
}

pair<ld, ld> equate(ld m, ld C, ll xi, ll yi)
{
  ld a = 1 + (m * m);
  ld b = 2 * m * C;
  ld c = C * C - r * r;
  if(b * b - 4 * a * c < 0) return {0, -1};
  
  ld x1 = -b + sqrtl(b * b - 4 * a * c);
  x1 /= 2 * a;

  ld x2 = -b - sqrtl(b * b - 4 * a * c);
  x2 /= 2 * a;
  
  ld y1 = m * x1 + c;
  ld y2 = m * x2 + c;

  pair<ll,ll> res;
  res = {TimE(yi, y1, m), TimE(yi, y2, m)};
  if(res.second < res.first) swap(res.second, res.first);

  return res;
}
// there is no change in 

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 ++)
    {
      ld dy = d[i] - b[i], dx = c[i] - a[i];
      pair<ld,ld> res;
      
      if(dy == 0 || dx == 0)
	{
	  if(dy == 0)
	    {
	      if(r*r >= b[i] * b[i])
		{
		  ld x = sqrtl(r * r - b[i] * b[i]);
		  res = {TimE(a[i], x, dx), TimE(a[i], -x, dx)};
		}
	    }
	  else
	    {
	      if(r * r <= a[i] * a[i])
		{
		  ld y = sqrtl(r * r - a[i] * a[i]);
		  res = {TimE(b[i], y, dy), TimE(b[i], -y, dy)};
		}
	    }
	  if(res.second < res.first) swap(res.second, res.first);
	}
      else
	{
	  
	  ld m = dy / dx;      
	  ld c = b[i] - a[i] * m;
	  res = equate(m, c, a[i], b[i]);
	}

      if(res.second < 0) continue;
      res.first = ceil(res.first);
      res.second = floor(res.second);
      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