Submission #639086

#	Time	Username	Problem	Language	Result	Execution time	Memory
639086		Pietra	Wish (LMIO19_noras)	C++14	0 / 100	0 ms	212 KiB

noras

#include<bits/stdc++.h>
#define int long long
using namespace std ;

const int maxn = 2e5 + 5 ;

int n, r, xi[maxn], xf[maxn], yi[maxn], yf[maxn] ;
vector<pair<int,int>> inter ;

bool test(int a, int b, int c, int x){ return (a*x*x + b*x + c <= 0) ; }

pair<int,int> bsk(int a, int b, int c){
    int d = (b*b) - (4*a*c) ;
    if(d < 0) return {1, 0} ;
    double k = (-b - sqrt(d))*1.00/(2*a*1.00) ;
    double k2 = (-b + sqrt(d))*1.00/(2*a*1.00) ;
    if(k < 0 && k2 < 0) return {1, 0} ;
    //cout << k << " " << k2 << "\n" ;
    if(k < 0) k = 0LL ;
    if(k2 < 0) k2 = 0LL ;
    //cout << a << " " << b << " " << c << " " << d << " " << k2 << "\n" ;
    return {k, k2} ;
}


int32_t main(){

    cin >> n >> r ;

    for(int i = 1 ; i <= n ; i++) cin >> xi[i] >> yi[i] >> xf[i] >> yf[i] ;

    for(int i = 1 ; i <= n ; i++){
        int dx = (xf[i]-xi[i]), dy = (yf[i]-yi[i]) ;
        int a = ((dx*dx)+(dy*dy)) ;
        int b = (2*xi[i]*dx) + (2*yi[i]*dy) ;
        int c = (xi[i]*xi[i]) + (yi[i]*yi[i]) - (r*r) ;
        //cout << a << " " << b << " " << c << "\n" ;
        pair<int,int> x = bsk(a, b, c) ;
        int tryy = x.first ;
        pair<int,int> kk = {-1, -1} ;
        for(int j = 0 ; j <= 3 ; j++) if(test(a, b, c, tryy + j)) kk.first = x.first + tryy ;
        for(int j = 0 ; j <= 3 ; j++) if(test(a, b, c, tryy - j)) kk.first = x.first - tryy ;
        tryy = x.second ;
        for(int j = 0 ; j <= 3 ; j++) if(test(a, b, c, tryy - j)) kk.second = x.second - tryy ;
        for(int j = 0 ; j <= 3 ; j++) if(test(a, b, c, tryy + j)) kk.second = x.second + tryy ;
        //cout << x.first << " " << x.second << " " << kk.first << " " << kk.second << "\n" ;
        if(kk.first > kk.second || kk.first == -1 || kk.second == -1 || x.first > x.second) continue ;
        inter.push_back({kk.first, 0}) ; inter.push_back({kk.second, 1}) ;
    }

    int ans = 0, sm = 0 ;

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

    for(auto a : inter){
        if(a.second) sm-- ;
        else sm++ ;
        ans = max(ans, sm) ;
    }

    cout << ans << "\n" ;

}

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