Cod sursa(job #1785776)

Utilizator enacheionutEnache Ionut enacheionut Data 21 octombrie 2016 22:31:57
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>

#define MAX 50000

using namespace std;

vector<vector<pair<int, int>>> cadrane(4);
set<int> drumuri;

pair<int, int> punctStart;

int numarPuncte;

void ImpartireInCadrane(pair<int, int> punct)
{
    if( punct.first > punctStart.first)
    {
        punct.second > punctStart.second  ?
            cadrane[0].push_back(punct) : ( punct.second = -punct.second, cadrane[1].push_back(punct) );
    }
    else
    {
        punct.first = -punct.first;
        punct.second > punctStart.second  ?
            cadrane[2].push_back(punct) : ( punct.second = -punct.second, cadrane[3].push_back(punct) );
    }
}

void CitireInput()
{
    ifstream in("pachete.in");
    in>> numarPuncte>> punctStart.first>> punctStart.second;
    for( int i = 1; i <= numarPuncte; ++i )
    {
        pair<int, int> punct;
        in>> punct.first>> punct.second;

        punct.first -= punctStart.first;
        punct.second -= punctStart.second;

        ImpartireInCadrane(punct);
    }
}

int DrumuriCurier()
{
    int numarDrumuri = 0;
    for( int i = 0; i <= 3; ++i )
    {
        sort( cadrane[i].begin(), cadrane[i].end() );
        drumuri.clear();
        for( unsigned int j = 0; j < cadrane[i].size(); ++j )
        {
            auto it = drumuri.lower_bound( cadrane[i][j].second );
            if( it != drumuri.end() )
            {
                drumuri.erase(it);
            }
            drumuri.insert(cadrane[i][j].second);
        }
        //cout<< "Drumuri.size() = " << drumuri.size()<<endl<<endl;
        numarDrumuri += drumuri.size();
    }

    return numarDrumuri;
}

int main ()
{
    CitireInput();

    ofstream out("pachete.out");
    out<< DrumuriCurier();

    out.close();
    return 0;
}