Submission #375752

#	Time	Username	Problem	Language	Result	Execution time	Memory
375752		mode149256	Wish (LMIO19_noras)	C++17	0 / 100	1 ms	364 KiB

noras

/*input
2 2
3 0 5 0
-2 1 2 1
*/
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

using ll = long long;
using pll = pair<ll, ll>;

const int MAX_N = 200005;
const ll INF = 2e9;

struct Star
{
	pll pos;
	pll dir;
};

int N;
ll R;
Star Stars[MAX_N];

pll getNth(pll pos, pll dir, ll n)
{
	if (n < 0) return {INF / 2, INF / 2};

	return make_pair(pos.F + n * dir.F, pos.S + n * dir.S);
}

ll getINF(pll dir)
{
	return INF / max(abs(dir.F), abs(dir.S));
}

ll closest(Star star)
{
	ll lo = 0, hi = getINF(star.dir);
	while (lo < hi)
	{
		ll mid = (lo + hi) / 2;
		pll pos1 = getNth(star.pos, star.dir, mid);
		pll pos2 = getNth(star.pos, star.dir, mid + 1);
		ll d1 = pos1.F * pos1.F + pos1.S * pos1.S;
		ll d2 = pos2.F * pos2.F + pos2.S * pos2.S;

		if (d1 == d2)
		{
			return mid;
		}
		else if (d1 < d2)
		{
			hi = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}

	return lo;
}

int main()
{
	scanf("%d%lld", &N, &R);

	for (int i = 0; i < N; i++)
	{
		ll a, b, c, d;
		scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
		Stars[i] = {{a, b}, {c - a, d - b}};
	}

	vector<pll> Intervals;

	for (int i = 0; i < N; i++)
	{
		ll close = closest(Stars[i]);
		pll closestPos = getNth(Stars[i].pos, Stars[i].dir, close);

		if (closestPos.F * closestPos.F + closestPos.S * closestPos.S > R * R)
			continue;

		ll l = close, r = close;

		ll did = getINF(Stars[i].dir);

		for (ll step = did; step > 0; step /= 2)
		{
			pll pos = getNth(Stars[i].pos, Stars[i].dir, l - step);
			if (pos.F * pos.F + pos.S * pos.S <= R * R)
			{
				l -= step;
			}
		}

		for (ll step = did; step > 0; step /= 2)
		{
			pll pos = getNth(Stars[i].pos, Stars[i].dir, r + step);
			if (pos.F * pos.F + pos.S * pos.S <= R * R)
			{
				r += step;
			}
		}

		//cerr << l << " " << r << endl;

		Intervals.push_back({l, 1});
		Intervals.push_back({r + 1, -1});
	}

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

	ll best = 0;
	ll curr = 0;

	for (pll p : Intervals)
	{
		curr += p.S;
		best = max(best, curr);
	}

	printf("%lld", best);

	return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d%lld", &N, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
noras.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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