Cod sursa(job #3257217)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 16 noiembrie 2024 22:07:59
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n, cnt = 0, sol[50010], rez = 0;
vector<int> cadran1, cadran2, cadran3, cadran4;

struct pereche {
    ///cine stie cunoaste
    int x, y;
    void read() { fin >> x >> y; }
}v[50010];
pereche start;

inline int cmp(int a, int b) { return v[a].x < v[b].x; }

int main()
{
    fin >> n;
    start.read();
    for(int i=1; i<=n; i++) {
        v[i].read();
        if(v[i].x <= start.x && v[i].y >= start.y) cadran1.push_back(i), v[i] = {start.x - v[i].x, v[i].y - start.y};
        else if(v[i].x >= start.x && v[i].y >= start.y) cadran2.push_back(i), v[i] = {v[i].x - start.x, v[i].y - start.y};
        else if(v[i].x >= start.x && v[i].y <= start.y) cadran3.push_back(i), v[i] = {v[i].x - start.x, start.y - v[i].y};
        else cadran4.push_back(i), v[i] = {start.x - v[i].x, start.y - v[i].y};
    }
    sort(cadran1.begin(), cadran1.end(), cmp);
    sort(cadran2.begin(), cadran2.end(), cmp);
    sort(cadran3.begin(), cadran3.end(), cmp);
    sort(cadran4.begin(), cadran4.end(), cmp);
    for(int i : cadran1) {
        int poz = lower_bound(sol+1, sol+cnt+1, v[i].y) - sol - 1;
        if(poz == cnt) sol[++cnt] = v[i].y;
        else sol[poz] = v[i].y;
    }
    rez += cnt, cnt = 0;
    for(int i : cadran2) {
        int poz = lower_bound(sol+1, sol+cnt+1, v[i].y) - sol - 1;
        if(poz == cnt) sol[++cnt] = v[i].y;
        else sol[poz] = v[i].y;
    }
    rez += cnt, cnt = 0;
    for(int i : cadran3) {
        int poz = lower_bound(sol+1, sol+cnt+1, v[i].y) - sol - 1;
        if(poz == cnt) sol[++cnt] = v[i].y;
        else sol[poz] = v[i].y;
    }
    rez += cnt, cnt = 0;
    for(int i : cadran4) {
        int poz = lower_bound(sol+1, sol+cnt+1, v[i].y) - sol - 1;
        if(poz == cnt) sol[++cnt] = v[i].y;
        else sol[poz] = v[i].y;
    }
    rez += cnt, cnt = 0;
    fout << rez;

    return 0;
}