Cod sursa(job #1390818)

Utilizator EpictetStamatin Cristian Epictet Data 17 martie 2015 12:59:51
Problema Pachete Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#define x first
#define y second
using namespace std;
ifstream fin ("pachete.in");
ofstream fout ("pachete.out");
int N, Ox, Oy, sol;
vector < pair < int, int > > C[5];

int Afla_Numarul_Minim_De_Drumuri(int l)
{
    int val = 0;
    list < pair < int, int > > L;
    for (int i = 0; i < C[l].size(); i++) L.push_back(C[l][i]);
    while (!L.empty())
    {
        int xx = 0, yy = 0;
        for (list < pair < int, int > > :: iterator it = L.begin(); it != L.end(); it++)
        {
            while (it != L.end() && it->y >= yy)
            {
                xx = it->x;
                yy = max (yy, it->y);
                it = L.erase(it);
            }
        }
        val++;
    }
    return val;
}

int main()
{
    fin >> N;
    fin >> Ox >> Oy;
    for (int xx, yy, i = 1; i <= N; i++)
    {
        fin >> xx >> yy;
        xx -= Ox;
        yy -= Oy;
        if (xx > 0 && yy > 0) C[1].push_back(make_pair(xx, yy));
        if (xx > 0 && yy < 0) C[2].push_back(make_pair(xx, -yy));
        if (xx < 0 && yy < 0) C[3].push_back(make_pair(-xx, -yy));
        if (xx < 0 && yy > 0) C[4].push_back(make_pair(-xx, yy));
    }

    for (int i = 1; i <= 4; i++)
    {
        sort (C[i].begin(), C[i].end());
        sol += Afla_Numarul_Minim_De_Drumuri(i);
    }


    fout << sol << '\n';
    fout.close();
    return 0;
}