Pagini recente » Cod sursa (job #2712981) | Cod sursa (job #83592) | Cod sursa (job #1524312) | Cod sursa (job #151770) | Cod sursa (job #1218036)
#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;
}