Cod sursa(job #1248586)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 25 octombrie 2014 16:18:52
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

void findandreplace(std::vector<int>& v, int elem) {
  // Find the largest smallest
  int li = 0, lf = v.size() - 1;
  int sol = -1;
  while (li <= lf) {
    int m = (li + lf) / 2;
    if (v[m] <= elem) {
      sol = m;
      lf = m - 1;
    } else {
      li = m + 1;
    }
  }
  if (sol == -1) {
    std::cerr << "Bad times!" << std::endl;
    return;
  }
  v[sol] = elem;
}

int solve(std::vector<std::pair<int, int> >& v) {
  std::vector<int> h;

  std::sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); ++i) {
    if (h.empty() || h[h.size() - 1] > v[i].second) {
      h.push_back(v[i].second);
    } else {
      findandreplace(h, v[i].second);
    }
  }

  return h.size();
}

int main()
{
  std::ifstream in("pachete.in");
  std::ofstream out("pachete.out");

  int n;
  std::pair<int, int> firma;
  std::vector<std::pair<int, int> > v[4];
  in >> n;
  in >> firma.first >> firma.second;
  for (int i = 0; i < n; ++i) {
    std::pair<int, int> p;
    in >> p.first >> p.second;
    if (p.first > firma.first) {
      if (p.second > firma.second) {
        v[0].push_back(make_pair(p.first - firma.first,
                                 p.second - firma.second));
      } else {
        v[1].push_back(make_pair(p.first - firma.second,
                                 firma.second - p.second));
      }
    } else {
      if (p.second > firma.second) {
        v[2].push_back(make_pair(firma.first - p.first,
                                 p.second - firma.second));
      } else {
        v[3].push_back(make_pair(firma.first - p.first,
                                 firma.second - p.second));
      }
    }
  }

  out << solve(v[0]) + solve(v[1]) + solve(v[2]) + solve(v[3]) << std::endl;

  in.close();
  out.close();

  return 0;
}