Cod sursa(job #1218036)

Utilizator diana97Diana Ghinea diana97 Data 9 august 2014 12:26:11
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

void citeste () {
    f >> n;
    f >> xi >> yi;
    long long 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(long long x) {
    int st = 1, 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 = 1; 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() - 1;

}

inline bool conditie1 (pair <int, int> a, pair <int, int> b) {
    return a.first<b.first;
}
inline bool conditie2 (pair <int, int> a, pair <int, int> b) {
    return a.first>b.first;
}

int main () {
    cadran[0].push_back(make_pair(-1, -1));
    cadran[1].push_back(make_pair(1, 1));
    cadran[2].push_back(make_pair(1, 1));
    cadran[3].push_back(make_pair(-1, -1));
    citeste();
    sort(cadran[0].begin(), cadran[0].end(), conditie1);
    sort(cadran[1].begin(), cadran[1].end(), conditie2);
    sort(cadran[2].begin(), cadran[2].end(), conditie2);
    sort(cadran[3].begin(), cadran[3].end(), conditie1);
    for (int i = 0; i < 4; i++) rezolva(i);
    g << solutie << '\n';
    return 0;
}