Pagini recente » Autentificare | Cod sursa (job #3345894)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
// #include <bits/std++.h>
#define in fin
#define out fout
#define int long long
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
struct punct{
int x, y;
};
bool cmp_universal(punct &a, punct &b){
if(a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
int nr_de_subsecvente(vector<int> &v){
if(v.empty()) return 0;
vector<int> capete;
for(int i = 0; i < v.size(); i++){
int l = 0, r = capete.size() - 1, sol = 0;
while(l <= r){
int m = (l + r) / 2;
if(capete[m] > v[i]){
l = m + 1;
sol = l + 1;
}else{
r = m - 1;
}
}
if(sol == capete.size()) capete.push_back(v[i]);
else capete[sol] = v[i];
}
return capete.size(); // nu e tocmai optim dar sa zicem
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
// de ce is totimpul asa tractor astea
int n; in >> n;
int xs, ys; in >> xs >> ys;
vector<punct> cdr[4];
for(int i = 0; i < n; i++){
int x, y; in >> x >> y;
x -= xs;
x -= ys; // translating
if(x < 0 && y > 0) cdr[0].push_back({-x, y});
if(x > 0 && y > 0) cdr[1].push_back({x, y});
if(x < 0 && y < 0) cdr[2].push_back({-x, -y});
if(x > 0 && y < 0) cdr[3].push_back({x, -y});
}
// sort dupa x bine si trb sa vad cate pot face cresc cu y
vector<int> minimude[4];
for(int i = 0; i < 4; i++){
sort(cdr[i].begin(), cdr[i].end(), cmp_universal);
for(int j = 0; j < cdr[i].size(); j++){
minimude[i].push_back(cdr[i][j].y);
}
}
int total = 0;
for(int i = 0; i < 4; i++){
total += nr_de_subsecvente(minimude[i]);
// cout << "i = " << i << " nr = " << nr_de_subsecvente(minimude[i]) << '\n';
// cout << "i = " << i << " v = ";
// for(const punct &x : cdr[i]) cout << "( " << x.x << " " << x.y << " ) ";
// cout << '\n';
}
out << total << '\n';
return 0;
}