Pagini recente » Cod sursa (job #2120600) | Cod sursa (job #2913108) | Cod sursa (job #2525916) | Cod sursa (job #3286823)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n, m, Ox, Oy;
vector<pair<int, int>> cadran[4]; // vectori pentru fiecare cadran
int k[4]; // numarul de drumuri pentru fiecare cadran
vector<int> d[4]; // retin cel mai mare Y pentru fiecare drum
// cauta binar in pozitia unde poate fi adaugat un punct intr-un drum extins
int binary_search(vector<int> &d, int y) {
int left = 0, right = d.size() - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (d[mid] > y) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
void adauga(vector<int> &d, int y) {
int pos = binary_search(d, y);
if (pos < d.size()) {
d[pos] = y;
} else d.push_back(y);
return;
}
int main()
{
fin >> n >> Ox >> Oy;
for (int i = 0; i < n; i++) {
int x, y;
fin >> x >> y;
x -= Ox, y -= Oy; // translatez fata de origine
if (x > 0 && y > 0) cadran[0].emplace_back(x, y);
else if (x < 0 && y > 0) cadran[1].emplace_back(-x, y);
else if (x < 0 && y < 0) cadran[2].emplace_back(-x, -y);
else cadran[3].emplace_back(x, -y);
}
// procesare pentru fiecare cadran
for (int i = 0; i < 4; i++) {
sort(cadran[i].begin(), cadran[i].end()); // sortare crescator dupa x apoi dupa y
for (auto &[x, y] : cadran[i]) {
adauga(d[i], y);
}
k[i] = d[i].size(); // numarul de drumuri pentru acest cadran
}
fout << k[0] + k[1] + k[2] + k[3];
return 0;
}