oj.uz

Submission #639096

# Submission time Handle Problem Language Result Execution time Memory
639096 2022-09-08T14:45:27 Z Pietra Wish (LMIO19_noras) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
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(double a, double b, double c){
    double 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} ;
    if(k < 0) k = 0LL ;
    if(k2 < 0) k2 = 0LL ;
    //cout << a << " " << b << " " << c << " " << d << " " << k2 << "\n" ;
    return {k, k2} ;
}


int 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, x.first + j)) kk.first = tryy + j ;
        for(int j = 0 ; j <= 3 && x.first - j >= 0 ; j++) if(test(a, b, c, x.first - j)) kk.first = tryy - j ;
        tryy = x.second ;
        for(int j = 0 ; j <= 3 && x.second - j >= 0 ; j++) if(test(a, b, c, x.second - j)) kk.second = tryy - j ;
        for(int j = 0 ; j <= 3 ; j++) if(test(a, b, c, x.second + j)) kk.second = tryy + j ;
        //cout << kk.first << " " << kk.second << "\n" ;
        if(kk.first > kk.second || kk.first == -1 || kk.second == -1) 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) cout << a.first << " " << a.second << "\n" ;

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

    cout << ans << "\n" ;

}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 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 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 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 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 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 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 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 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -