Cod sursa(job #2850114)

Utilizator rares89_Dumitriu Rares rares89_ Data 16 februarie 2022 11:52:39
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pachete.in");
ofstream fout("pachete.out");

int n, x, y, d[50005], X, Y;
vector< pair<int, int> > v[5];

/*
v[1] - punctele din cadranul 1
v[2] - punctele din cadranul 2
..
*/

int caut(int x) {
    int cnt = 0;
    for(unsigned int i = 0; i < v[x].size(); i++){
        int st = 1, dr = cnt;
        while(st <= dr){
            int mid = (st + dr) / 2;
            if(v[x][i].second >= d[mid]) {
                dr = mid - 1;
            } else {
                st = mid + 1;
            }
        }
        if(st > cnt) {
            cnt++;
        }
        d[st] = v[x][i].second;
    }
    return cnt;
}

int main() {
    fin >> n >> x >> y;
    for(int i = 1; i <= n; i++) {
        fin >> X >> Y;
        X -= x;
        Y -= y;
        if(X >= 0) {
            if(Y >= 0) {
                v[1].push_back({X, Y});
            } else {
                v[4].push_back({X, Y});
            }
        } else {
            if(Y >= 0) {
                v[2].push_back({X, Y});
            } else {
                v[3].push_back({X, Y});
            }
        }
    }
    fin.close();
    
    int sol = 0;
    
    sort(v[1].begin(), v[1].end());
    sol += caut(1);
    
    sort(v[2].begin(), v[2].end());
    sol += caut(2);
    
    sort(v[3].begin(), v[3].end());
    sol += caut(3);
    
    sort(v[4].begin(), v[4].end());
    sol += caut(4);
 
    fout << sol;
 
    return 0;
}