Cod sursa(job #1217645)

Utilizator diana97Diana Ghinea diana97 Data 7 august 2014 21:00:54
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, xi, yi, solutie;
vector< pair<int, int> > cadran[4];
vector <int> sol;

void citeste () {
    f >> n;
    f >> xi >> yi;
    int x, y, c;
    for (int i = 1; i <= n; i++) {
        f >> x >> y;
        x -= xi;
        y -= yi;
        if (x > 0) {
            if (y > 0) c = 0;
            else c = 3;
        }
        else {
            if (y > 0) c = 1;
            else c = 2;
        }
        cadran[c].push_back(make_pair(x, y));
    }
}

int cauta(int x) {
    int st = 0, dr = sol.size() - 1, mid;
    int rez = 0;
    while (st <= dr) {
        mid = (st + dr) / 2;
        if (x < sol[mid]) st = mid + 1;
        else {
            dr = mid - 1;
            rez = mid;
        }
    }
    return rez;
}

void rezolva (int c) {
    sol.clear();
    //sol.push_back(1);
    int n = cadran[c].size();
    for (int i = 0; i < n; i++) {
        //cout << cadran[c][i].second;
        int poz = cauta(cadran[c][i].second);
        if (poz == 0) sol.push_back(cadran[c][i].second);
        else sol[poz] = cadran[c][i].second;
    }
    solutie += sol.size();

}

int main () {
    citeste();
    for (int i = 0; i < 4; i++) sort(cadran[i].begin(), cadran[i].end());
    for (int i = 0; i < 4; i++) rezolva(i);
    g << solutie << '\n';
    return 0;
}