Submission #1164840

#TimeUsernameProblemLanguageResultExecution timeMemory
1164840MuhammadSaramWish (LMIO19_noras)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
	int n,R;
	cin>>n>>R;
	int 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<int> v,v1;
	set<int> se;
	for (int i=0;i<n;i++)
	{
		if (b[i]<=R)
		{
			c[i]-=a[i];
			int x=sqrtl(R*R-b[i]*b[i]);
			if (c[i]<0)
			{
				int s=-1,e=1e9;
				while (s+1<e)
				{
					int mid=(s+e)/2;
					if (c[i]*mid+a[i]<=x)
						e=mid;
					else
						s=mid;
				}
				int l=e;
				s=0,e=1e9;
				while (s+1<e)
				{
					int mid=(s+e)/2;
					if (c[i]*mid+a[i]>=-x)
						s=mid;
					else
						e=mid;
				}
				if (s>=l)
					v.push_back(l),v1.push_back(s);
			}
			else
			{
				int s=-1,e=1e9;
				while (s+1<e)
				{
					int mid=(s+e)/2;
					if (c[i]*mid+a[i]>=-x)
						e=mid;
					else
						s=mid;
				}
				int l=e;
				s=0,e=1e9;
				while (s+1<e)
				{
					int mid=(s+e)/2;
					if (c[i]*mid+a[i]<=x)
						s=mid;
					else
						e=mid;
				}
				if (s>=l)
					v.push_back(l),v1.push_back(s);
			}
			if (!v.empty())
				se.insert(v.back()),se.insert(v1.back());
		}
	}
	sort(v.begin(),v.end());
	sort(v1.begin(),v1.end());
	int ans=0,id=0,id1=0;
	for (int i:se)
	{
		while (id<v.size() && v[id]<=i)
			id++;
		while (id1<v1.size() && v1[id1]<i)
			id1++;
		ans=max(ans,id-id1);
	}
	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...