Cod sursa(job #1514110)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 octombrie 2015 16:28:59
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

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

const int MAX_N = 50000;

struct Point {
    int x;
    int y;
};

vector < Point > Q1, Q2, Q3, Q4, V;
set < int, greater < int > > S;
set < int, greater < int > > :: iterator it;

bool pSort(Point A, Point B) {
    return A.y < B.y;
}

int countPartitions() {
    int i;

    if(V.empty()) return 0;

    sort(V.begin(), V.end(), pSort);

    S.clear();
    S.insert(V[0].x);
    for(i = 1; i < V.size(); i++) {
        it = S.lower_bound(V[i].x);
        if(it == S.end()) {
            S.insert(V[i].x);
        }
        else {
            it--;
            S.erase(it);
            S.insert(V[i].x);
        }
    }

    return S.size();
}

int main() {
    int n, i, ox, oy, x, y, ans = 0;

    in >> n;
    in >> ox >> oy;

    for(i = 1; i <= n; i++) {
        in >> x >> y;
        x -= ox;
        y -= oy;

        if(x > 0 && y > 0) {
            Q1.push_back({x, y});
        }
        else if(x > 0 && y < 0) {
            Q2.push_back({x, -y});
        }
        else if(x < 0 && y < 0) {
            Q3.push_back({-x, -y});
        }
        else {
            Q4.push_back({-x, y});
        }
    }

    V = Q1;
    ans += countPartitions();
    V = Q2;
    ans += countPartitions();
    V = Q3;
    ans += countPartitions();
    V = Q4;
    ans += countPartitions();

    out << ans << '\n';

    return 0;
}