Pagini recente » Cod sursa (job #2369202) | Cod sursa (job #632268) | Cod sursa (job #2916073) | Cod sursa (job #1702460) | Cod sursa (job #1248586)
#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;
}