Pagini recente » Cod sursa (job #3276620) | Cod sursa (job #3236421) | Cod sursa (job #2979668) | Cod sursa (job #3293207) | Cod sursa (job #3257212)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n, cnt = 0, sol[50010], rez = 0;
vector<int> cadran1, cadran2, cadran3, cadran4;
struct pereche {
///cine stie cunoaste
int x, y;
void read() { fin >> x >> y; }
}v[50010];
pereche start;
inline int cmpCresc(int a, int b) { return v[a].x < v[b].x; }
inline int cmpDescr(int a, int b) { return v[a].x > v[n].x; }
int main()
{
fin >> n;
start.read();
for(int i=1; i<=n; i++) {
v[i].read();
if(v[i].x <= start.x && v[i].y >= start.y) cadran1.push_back(i);
else if(v[i].x >= start.x && v[i].y >= start.y) cadran2.push_back(i);
else if(v[i].x >= start.x && v[i].y <= start.y) cadran3.push_back(i);
else cadran4.push_back(i);
}
sort(cadran1.begin(), cadran1.end(), cmpDescr);
sort(cadran2.begin(), cadran2.end(), cmpCresc);
sort(cadran3.begin(), cadran3.end(), cmpCresc);
sort(cadran4.begin(), cadran4.end(), cmpDescr);
for(int i : cadran1) {
int st = 1, dr = cnt, ans = -1;
while(st <= dr) {
int mid = (st + dr) / 2;
if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
else st = mid + 1;
}
if(ans == -1) sol[++cnt] = v[i].y;
else sol[ans] = v[i].y;
}
rez += cnt, cnt = 0;
for(int i : cadran2) {
int st = 1, dr = cnt, ans = -1;
while(st <= dr) {
int mid = (st + dr) / 2;
if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
else st = mid + 1;
}
if(ans == -1) sol[++cnt] = v[i].y;
else sol[ans] = v[i].y;
}
rez += cnt, cnt = 0;
for(int i : cadran3) {
int st = 1, dr = cnt, ans = -1;
while(st <= dr) {
int mid = (st + dr) / 2;
if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
else st = mid + 1;
}
if(ans == -1) sol[++cnt] = v[i].y;
else sol[ans] = v[i].y;
}
rez += cnt, cnt = 0;
for(int i : cadran4) {
int st = 1, dr = cnt, ans = -1;
while(st <= dr) {
int mid = (st + dr) / 2;
if(sol[mid] <= v[i].y) ans = max(ans, mid), dr = mid - 1;
else st = mid + 1;
}
if(ans == -1) sol[++cnt] = v[i].y;
else sol[ans] = v[i].y;
}
rez += cnt, cnt = 0;
fout << rez;
return 0;
}