답안 #638408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638408 2022-09-05T21:01:36 Z LeticiaFCS Wish (LMIO19_noras) C++17
93 / 100
167 ms 14872 KB
#include "bits/stdc++.h"
#define st first
#define nd second
using lint = int64_t;
constexpr int MOD = int(1e9) + 7;
constexpr int INF = 0x3f3f3f3f;
constexpr int NINF = 0xcfcfcfcf;
constexpr lint LINF = 0x3f3f3f3f3f3f3f3f;
const long double PI = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;


using ld = long double;



bool inCircle(lint x, lint y, lint dx, lint dy, lint r, lint t){
	return (x + dx*t)*(x + dx*t) + (y + dy*t)*(y + dy*t) <= r*r; 
}
pair<bool, lint> firstInCircle(lint x, lint y, lint dx, lint dy, lint r, ld dbt){	
	lint t = ceil(dbt) - 1;
	if(inCircle(x,y,dx,dy,r, t)) return {true,t};
	t++;
	if(inCircle(x,y,dx,dy,r, t)) return {true,t};
	t++;
	if(inCircle(x,y,dx,dy,r, t)) return {true,t};
	return {false, -1};
}
pair<bool, lint> lastInCircle(lint x, lint y, lint dx, lint dy, lint r, ld dbt){	
	lint t = floor(dbt) + 1;
	if(inCircle(x,y,dx,dy,r, t)) return {true,t};
	t--;
	if(inCircle(x,y,dx,dy,r, t)) return {true,t};
	t--;
	if(inCircle(x,y,dx,dy,r, t)) return {true,t};
	return {false, -1};
}


vector<lint> intersection(lint x, lint y, lint dx, lint dy, lint r){
	vector<lint> answer;
	
	lint a = (dx*dx + dy*dy);
	lint b = (2*x*dx + 2*y*dy);
	lint c = -(r*r - x*x - y*y);
	lint delta = b*b - 4*a*c;
	
	if(delta < 0) return answer;
	if(delta == 0){
		ld t = ld(-b) / ld(2*a);
		auto left = firstInCircle(x,y,dx,dy,r,t);
		if(!left.first) return {};
		auto right = lastInCircle(x,y,dx,dy,r,t);
		if(!right.first) return {};
		answer = {left.second, right.second};
		return answer;
	}
	auto left = firstInCircle(x,y,dx,dy,r, ( ld(-b) - sqrtl((ld)delta))/ ld(2*a) );
	if(!left.first) return {};
	auto right = lastInCircle(x,y,dx,dy,r, (ld(-b) + sqrtl((ld)delta))/ ld(2*a) );
	if(!right.first) return {};
	
	answer = {left.second, right.second};
	if(answer[0] > answer[1]) answer = {};
	if(answer.back() < 0) answer = {};
	else if(answer[0] < 0) answer[0] = 0;
	
	return answer;
}

vector<lint> comprTime;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	comprTime = {-1};
	int n, r; cin>>n>>r;
	vector<vector<lint>> stars;
	for(int i=0; i<n; i++){
		int x1, y1, x2, y2;
		cin>>x1>>y1>>x2>>y2;
		auto v = intersection(x1, y1, x2-x1, y2-y1, r);
		if(!v.empty()){
			stars.push_back(v);
			comprTime.push_back(v[0]);
			comprTime.push_back(v[1]);
		}
	}
	sort(comprTime.begin(), comprTime.end());
	comprTime.resize(distance(
		comprTime.begin(),
		unique(comprTime.begin(), comprTime.end())	
	));
	comprTime.push_back(comprTime.back()+1);
	
	vector<lint> pref(comprTime.size());
	for(auto star : stars){
		int l = lower_bound(comprTime.begin(),comprTime.end(), star[0]) - comprTime.begin();
		int r = upper_bound(comprTime.begin(),comprTime.end(), star[1]) - comprTime.begin();
		pref[l]++;
		pref[r]--;
	}
	for(int i=1; i<int(comprTime.size()); i++)
		pref[i] += pref[i-1];
	cout<<*max_element(pref.begin(), pref.end())<<"\n";
	

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
23 Correct 56 ms 7340 KB Output is correct
24 Correct 54 ms 7240 KB Output is correct
25 Correct 54 ms 7312 KB Output is correct
26 Correct 57 ms 7276 KB Output is correct
27 Correct 52 ms 3980 KB Output is correct
28 Correct 54 ms 6664 KB Output is correct
29 Correct 55 ms 6688 KB Output is correct
30 Correct 48 ms 6728 KB Output is correct
31 Correct 55 ms 6708 KB Output is correct
32 Correct 66 ms 7308 KB Output is correct
33 Correct 71 ms 7352 KB Output is correct
34 Correct 73 ms 7340 KB Output is correct
35 Correct 69 ms 7244 KB Output is correct
36 Correct 71 ms 7344 KB Output is correct
37 Correct 46 ms 5108 KB Output is correct
38 Correct 49 ms 5136 KB Output is correct
39 Correct 68 ms 3996 KB Output is correct
40 Correct 45 ms 4360 KB Output is correct
41 Correct 47 ms 4008 KB Output is correct
42 Correct 46 ms 3992 KB Output is correct
43 Correct 148 ms 14868 KB Output is correct
44 Correct 153 ms 14812 KB Output is correct
45 Correct 158 ms 14792 KB Output is correct
46 Correct 149 ms 14796 KB Output is correct
47 Correct 151 ms 14872 KB Output is correct
48 Correct 138 ms 14096 KB Output is correct
49 Correct 144 ms 14180 KB Output is correct
50 Correct 139 ms 14052 KB Output is correct
51 Correct 130 ms 14116 KB Output is correct
52 Correct 148 ms 14132 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 352 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 464 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
23 Correct 56 ms 7340 KB Output is correct
24 Correct 54 ms 7240 KB Output is correct
25 Correct 54 ms 7312 KB Output is correct
26 Correct 57 ms 7276 KB Output is correct
27 Correct 52 ms 3980 KB Output is correct
28 Correct 54 ms 6664 KB Output is correct
29 Correct 55 ms 6688 KB Output is correct
30 Correct 48 ms 6728 KB Output is correct
31 Correct 55 ms 6708 KB Output is correct
32 Correct 66 ms 7308 KB Output is correct
33 Correct 71 ms 7352 KB Output is correct
34 Correct 73 ms 7340 KB Output is correct
35 Correct 69 ms 7244 KB Output is correct
36 Correct 71 ms 7344 KB Output is correct
37 Correct 46 ms 5108 KB Output is correct
38 Correct 49 ms 5136 KB Output is correct
39 Correct 68 ms 3996 KB Output is correct
40 Correct 45 ms 4360 KB Output is correct
41 Correct 47 ms 4008 KB Output is correct
42 Correct 46 ms 3992 KB Output is correct
43 Correct 148 ms 14868 KB Output is correct
44 Correct 153 ms 14812 KB Output is correct
45 Correct 158 ms 14792 KB Output is correct
46 Correct 149 ms 14796 KB Output is correct
47 Correct 151 ms 14872 KB Output is correct
48 Correct 138 ms 14096 KB Output is correct
49 Correct 144 ms 14180 KB Output is correct
50 Correct 139 ms 14052 KB Output is correct
51 Correct 130 ms 14116 KB Output is correct
52 Correct 148 ms 14132 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 352 KB Output is correct
57 Correct 1 ms 332 KB Output is correct
58 Correct 1 ms 464 KB Output is correct
59 Correct 55 ms 7248 KB Output is correct
60 Correct 50 ms 3764 KB Output is correct
61 Correct 51 ms 4020 KB Output is correct
62 Correct 54 ms 4440 KB Output is correct
63 Correct 60 ms 3876 KB Output is correct
64 Correct 59 ms 3644 KB Output is correct
65 Correct 60 ms 3788 KB Output is correct
66 Correct 59 ms 3864 KB Output is correct
67 Correct 64 ms 3776 KB Output is correct
68 Correct 76 ms 7352 KB Output is correct
69 Correct 66 ms 7324 KB Output is correct
70 Correct 66 ms 7356 KB Output is correct
71 Correct 72 ms 7244 KB Output is correct
72 Correct 70 ms 7296 KB Output is correct
73 Correct 47 ms 4752 KB Output is correct
74 Correct 50 ms 6696 KB Output is correct
75 Correct 55 ms 6704 KB Output is correct
76 Correct 42 ms 4200 KB Output is correct
77 Correct 145 ms 13220 KB Output is correct
78 Correct 151 ms 13200 KB Output is correct
79 Correct 153 ms 13228 KB Output is correct
80 Correct 152 ms 13204 KB Output is correct
81 Correct 158 ms 13264 KB Output is correct
82 Correct 142 ms 14148 KB Output is correct
83 Correct 136 ms 14136 KB Output is correct
84 Correct 142 ms 14000 KB Output is correct
85 Correct 146 ms 13908 KB Output is correct
86 Correct 167 ms 13996 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
23 Correct 56 ms 7340 KB Output is correct
24 Correct 54 ms 7240 KB Output is correct
25 Correct 54 ms 7312 KB Output is correct
26 Correct 57 ms 7276 KB Output is correct
27 Correct 52 ms 3980 KB Output is correct
28 Correct 54 ms 6664 KB Output is correct
29 Correct 55 ms 6688 KB Output is correct
30 Correct 48 ms 6728 KB Output is correct
31 Correct 55 ms 6708 KB Output is correct
32 Correct 66 ms 7308 KB Output is correct
33 Correct 71 ms 7352 KB Output is correct
34 Correct 73 ms 7340 KB Output is correct
35 Correct 69 ms 7244 KB Output is correct
36 Correct 71 ms 7344 KB Output is correct
37 Correct 46 ms 5108 KB Output is correct
38 Correct 49 ms 5136 KB Output is correct
39 Correct 68 ms 3996 KB Output is correct
40 Correct 45 ms 4360 KB Output is correct
41 Correct 47 ms 4008 KB Output is correct
42 Correct 46 ms 3992 KB Output is correct
43 Correct 148 ms 14868 KB Output is correct
44 Correct 153 ms 14812 KB Output is correct
45 Correct 158 ms 14792 KB Output is correct
46 Correct 149 ms 14796 KB Output is correct
47 Correct 151 ms 14872 KB Output is correct
48 Correct 138 ms 14096 KB Output is correct
49 Correct 144 ms 14180 KB Output is correct
50 Correct 139 ms 14052 KB Output is correct
51 Correct 130 ms 14116 KB Output is correct
52 Correct 148 ms 14132 KB Output is correct
53 Correct 55 ms 7248 KB Output is correct
54 Correct 50 ms 3764 KB Output is correct
55 Correct 51 ms 4020 KB Output is correct
56 Correct 54 ms 4440 KB Output is correct
57 Correct 60 ms 3876 KB Output is correct
58 Correct 59 ms 3644 KB Output is correct
59 Correct 60 ms 3788 KB Output is correct
60 Correct 59 ms 3864 KB Output is correct
61 Correct 64 ms 3776 KB Output is correct
62 Correct 76 ms 7352 KB Output is correct
63 Correct 66 ms 7324 KB Output is correct
64 Correct 66 ms 7356 KB Output is correct
65 Correct 72 ms 7244 KB Output is correct
66 Correct 70 ms 7296 KB Output is correct
67 Correct 47 ms 4752 KB Output is correct
68 Correct 50 ms 6696 KB Output is correct
69 Correct 55 ms 6704 KB Output is correct
70 Correct 42 ms 4200 KB Output is correct
71 Correct 145 ms 13220 KB Output is correct
72 Correct 151 ms 13200 KB Output is correct
73 Correct 153 ms 13228 KB Output is correct
74 Correct 152 ms 13204 KB Output is correct
75 Correct 158 ms 13264 KB Output is correct
76 Correct 142 ms 14148 KB Output is correct
77 Correct 136 ms 14136 KB Output is correct
78 Correct 142 ms 14000 KB Output is correct
79 Correct 146 ms 13908 KB Output is correct
80 Correct 167 ms 13996 KB Output is correct
81 Correct 1 ms 212 KB Output is correct
82 Correct 1 ms 340 KB Output is correct
83 Correct 1 ms 340 KB Output is correct
84 Correct 1 ms 352 KB Output is correct
85 Correct 1 ms 332 KB Output is correct
86 Correct 1 ms 464 KB Output is correct
87 Incorrect 61 ms 3528 KB Output isn't correct
88 Halted 0 ms 0 KB -