Cod sursa(job #1514101)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 octombrie 2015 16:19:46
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 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;
set < int > S;

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

int countPartitions(vector < Point > V) {
    set < int, greater < int > > S;
    set < int, greater < int > > :: iterator it;
    int i;

    if(V.empty()) return 0;

    sort(V.begin(), V.end(), pSort);
    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;

    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});
        }
    }

    out << countPartitions(Q1) + countPartitions(Q2) + countPartitions(Q3) + countPartitions(Q4);
    return 0;
}