Pagini recente » Cod sursa (job #2627768) | Cod sursa (job #737840) | Cod sursa (job #1790900) | Cod sursa (job #1273232) | Cod sursa (job #1514110)
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
ifstream in("pachete.in");
ofstream out("pachete.out");
const int MAX_N = 50000;
struct Point {
int x;
int y;
};
vector < Point > Q1, Q2, Q3, Q4, V;
set < int, greater < int > > S;
set < int, greater < int > > :: iterator it;
bool pSort(Point A, Point B) {
return A.y < B.y;
}
int countPartitions() {
int i;
if(V.empty()) return 0;
sort(V.begin(), V.end(), pSort);
S.clear();
S.insert(V[0].x);
for(i = 1; i < V.size(); i++) {
it = S.lower_bound(V[i].x);
if(it == S.end()) {
S.insert(V[i].x);
}
else {
it--;
S.erase(it);
S.insert(V[i].x);
}
}
return S.size();
}
int main() {
int n, i, ox, oy, x, y, ans = 0;
in >> n;
in >> ox >> oy;
for(i = 1; i <= n; i++) {
in >> x >> y;
x -= ox;
y -= oy;
if(x > 0 && y > 0) {
Q1.push_back({x, y});
}
else if(x > 0 && y < 0) {
Q2.push_back({x, -y});
}
else if(x < 0 && y < 0) {
Q3.push_back({-x, -y});
}
else {
Q4.push_back({-x, y});
}
}
V = Q1;
ans += countPartitions();
V = Q2;
ans += countPartitions();
V = Q3;
ans += countPartitions();
V = Q4;
ans += countPartitions();
out << ans << '\n';
return 0;
}