Submission #670724

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670724	2022-12-10T01:22:25 Z	thiago_bastos	Wish (LMIO19_noras)	C++17	0 / 100	22 ms	396 KB

noras

#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

#define double ld

int n, radius;

double closest(int a, int b, int c, int d) {
	if(1ll*a*a+1ll*b*b <= 1ll * radius*radius) return 0;
	double l = 0, r = 1e9;
	while(fabs(l - r) > EPS) {
		double L = (2 * l + r) / 3.0, R = (2 * r + l) / 3.0;
		if(hypot(a + L * c, b + L * d) > hypot(a + R * c, b + R * d)) l = L;
		else r = R;
	}
	return r;
}

double firstSec(int a, int b, int c, int d, double k) {
	double l = 0, r = k;
	while(fabs(l - r) > EPS) {
		double m = (l + r) / 2;
		if(hypot(a + m * c, b + m * d) <= radius) r = m;
		else l = m;
	}
	return r;
}

double secondSec(int a, int b, int c, int d, double k) {
	double l = k, r = 1e9;
	while(fabs(l - r) > EPS) {
		double m = (l + r) / 2;
		if(hypot(a + m * c, b + m * d) > radius) r = m;
		else l = m;
	}
	return r;
}

void solve() {
	cin >> n >> radius;

	set<ii> sweep;
	int opening = 0, ans = 0;

	for(int i = 1; i <= n; ++i) {
		int a, b, c, d;

		cin >> a >> b >> c >> d;

		c -= a, d -= b;

		double k = closest(a, b, c, d);
		double l = firstSec(a, b, c, d, k);
		double r = secondSec(a, b, c, d, k);

		if(hypot(a + k * c, b + k * d) > radius) continue;	
		
		int L = (int)ceil(l), R = floor(r);
		
		if(L > R) continue;

		sweep.emplace(L, -i);
		sweep.emplace(R, i);
	}

	for(auto [x, k] : sweep) {
		opening += k < 0 ? 1 : -1;
		ans = max(ans, opening);
	}
	
	cout << ans << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	17 ms	212 KB	Output is correct
4	Correct	17 ms	352 KB	Output is correct
5	Correct	18 ms	344 KB	Output is correct
6	Correct	17 ms	332 KB	Output is correct
7	Correct	17 ms	344 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	22 ms	380 KB	Output is correct
15	Correct	22 ms	356 KB	Output is correct
16	Correct	22 ms	340 KB	Output is correct
17	Correct	22 ms	396 KB	Output is correct
18	Correct	22 ms	340 KB	Output is correct
19	Incorrect	21 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #2
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	17 ms	212 KB	Output is correct
4	Correct	17 ms	352 KB	Output is correct
5	Correct	18 ms	344 KB	Output is correct
6	Correct	17 ms	332 KB	Output is correct
7	Correct	17 ms	344 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	22 ms	380 KB	Output is correct
15	Correct	22 ms	356 KB	Output is correct
16	Correct	22 ms	340 KB	Output is correct
17	Correct	22 ms	396 KB	Output is correct
18	Correct	22 ms	340 KB	Output is correct
19	Incorrect	21 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	17 ms	212 KB	Output is correct
4	Correct	17 ms	352 KB	Output is correct
5	Correct	18 ms	344 KB	Output is correct
6	Correct	17 ms	332 KB	Output is correct
7	Correct	17 ms	344 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	22 ms	380 KB	Output is correct
15	Correct	22 ms	356 KB	Output is correct
16	Correct	22 ms	340 KB	Output is correct
17	Correct	22 ms	396 KB	Output is correct
18	Correct	22 ms	340 KB	Output is correct
19	Incorrect	21 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	17 ms	212 KB	Output is correct
4	Correct	17 ms	352 KB	Output is correct
5	Correct	18 ms	344 KB	Output is correct
6	Correct	17 ms	332 KB	Output is correct
7	Correct	17 ms	344 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	22 ms	380 KB	Output is correct
15	Correct	22 ms	356 KB	Output is correct
16	Correct	22 ms	340 KB	Output is correct
17	Correct	22 ms	396 KB	Output is correct
18	Correct	22 ms	340 KB	Output is correct
19	Incorrect	21 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #5
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	17 ms	212 KB	Output is correct
4	Correct	17 ms	352 KB	Output is correct
5	Correct	18 ms	344 KB	Output is correct
6	Correct	17 ms	332 KB	Output is correct
7	Correct	17 ms	344 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	22 ms	380 KB	Output is correct
15	Correct	22 ms	356 KB	Output is correct
16	Correct	22 ms	340 KB	Output is correct
17	Correct	22 ms	396 KB	Output is correct
18	Correct	22 ms	340 KB	Output is correct
19	Incorrect	21 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Submission #670724

Compilation message

Subtask #1 0 / 23.0

Subtask #2 0 / 23.0

Subtask #3 0 / 15.0

Subtask #4 0 / 32.0

Subtask #5 0 / 7.0

Subtask #1
0 / 23.0

Subtask #2
0 / 23.0

Subtask #3
0 / 15.0

Subtask #4
0 / 32.0

Subtask #5
0 / 7.0