Submission #783639

#	Time	Username	Problem	Language	Result	Execution time	Memory
783639		vjudge1	Wish (LMIO19_noras)	C++17	0 / 100	1 ms	212 KiB

noras

#include <bits/stdc++.h>
using namespace std;
int n, r;
 
long double near(int a, int b, int c, int d) {
	if(1LL*a*a+1LL*b*b <= 1LL*r*r) return 0;
	return max(0.0L, (-1LL*a*c-1LL*b*d)/(long double)(1LL*c*c+1LL*d*d));
}
 
long double firstSec(int a, int b, int c, int d, long double k) {
	long double l=0, r=k;
	while(fabs(l-r)>1e-12L){
		long double m=(l+r)/2.0;
        long double x=a+m*c, y=b+m*d;
		if(x*x+y*y<=1LL*r*r){
            r=m;
        }else{
            l=m;
        }
	}
	return r;
}
 
long double secondSec(int a, int b, int c, int d, long double k) {
	long double l=k, r=1e9;
	while(fabs(l-r)>1e-12L){
		long double m=(l+r)/2;
		long double x=a+m*c, y=b+m*d;
		if(abs(x)>1e9 || abs(y)>1e9 || x*x+y*y>1LL*r*r){
            r=m;
        }else{
            l=m;
        }
	}
	return r;
}

 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
    cin >> n >> r;
	set<pair<int, int>> st;
	int op=0, ans=0;
 
	for(int i=1; i<=n; i++){
        int a, b, c, d;
		cin >> a >> b >> c >> d;
		c-=a;
        d-=b;
		long double k=near(a, b, c, d);
		if(hypot(a+k*c, b+k*d)-r>1e-12L) continue;	
		long double l=firstSec(a, b, c, d, k), r=secondSec(a, b, c, d, k);
		long long left=(int)ceil(l), right=floor(r);
		if(left>right) continue;
		st.emplace(left, -i);
		st.emplace(right, i);
	}
	for(auto [a, b]:st){
        if(b<0){
            op++;
        }else{
            op--;
        }
		ans=max(ans, op);
	}
	cout << ans << endl;
} 

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