Pagini recente » Cod sursa (job #346794) | Cod sursa (job #2898130) | Cod sursa (job #1690934) | Cod sursa (job #1187324) | Cod sursa (job #2113931)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <cstring>
#define MAX_VAL 50005
#define INPUT "pachete.in"
#define OUTPUT "pachete.out"
using namespace std;
ifstream f (INPUT );
ofstream g (OUTPUT);
int n, X, Y, x, y, yMaxA, yMaxB, maxA, maxB, Sol[MAX_VAL], ans;
struct str{
int x, y;
}a1[MAX_VAL], b1[MAX_VAL], a2[MAX_VAL], b2[MAX_VAL];
bool cmp( str a, str b ){
return a.x < b.x;
}
bool cmp1( str a, str b ){
return a.x > b.x;
}
int binSearch(int lt, int rt, int val){
int mid;
while( lt <= rt ){
mid = (lt+rt)/2;
if( Sol[mid-1] > val && val >= Sol[mid] )
return mid;
else if( Sol[mid] < val )
rt = mid - 1;
else
lt = mid + 1;
}
return lt;
}
int binSearch1(int lt, int rt, int val){
int mid;
while( lt <= rt ){
mid = (lt+rt)/2;
if( Sol[mid-1] < val && val <= Sol[mid] )
return mid;
else if( Sol[mid] > val )
rt = mid - 1;
else
lt = mid + 1;
}
return lt;
}
int main(){
f >> n;
f >> X >> Y;
for(int i = 1; i <= n; i++){
f >> x >> y;
if( y > Y ){
if( x < X ){
a1[++a1[0].x].x = x;
a1[a1[0].x].y = y;
}
else{
a2[++a2[0].x].x = x;
a2[a2[0].x].y = y;
}
}
else{
if( x < X ){
b1[++b1[0].x].x = x;
b1[b1[0].x].y = y;
}
else{
b2[++b2[0].x].x = x;
b2[b2[0].x].y = y;
}
}
}
sort( a1+1, a1+a1[0].x+1, cmp1);
sort( a2+1, a2+a2[0].x+1, cmp);
sort( b1+1, b1+b1[0].x+1, cmp1);
sort( b2+1, b2+b2[0].x+1, cmp);
int nr = 0, poz = 0;
Sol[0] = 1000000000;
for(int i = 1; i <= a1[0].x; i++){
poz = binSearch(1, nr+1, a1[i].y);
if(poz == nr+1)
nr++;
Sol[poz] = a1[i].y;
}
ans += nr;
nr = 0;
memset(Sol, 0, sizeof(Sol));
Sol[0] = 1000000000;
for(int i = 1; i <= a2[0].x; i++){
poz = binSearch(1, nr+1, a2[i].y);
if(poz == nr+1)
nr++;
Sol[poz] = a2[i].y;
}
ans += nr;
for(int i = 1; i <= nr; i++)
Sol[i] = 1000000000;
nr = 0;
Sol[0] = -1000000000;
Sol[1] = 1000000000;
for(int i = 1; i <= b1[0].x; i++){
poz = binSearch1(1, nr+1, b1[i].y);
if(poz >= nr+1)
nr++;
Sol[poz] = b1[i].y;
}
ans += nr;
Sol[0] = -1000000000;
for(int i = 1; i <= nr; i++)
Sol[i] = 1000000000;
nr = 0;
for(int i = 1; i <= b2[0].x; i++){
poz = binSearch1(1, nr+1, b2[i].y);
if(poz >= nr+1)
nr++;
Sol[poz] = b2[i].y;
}
ans += nr;
g << ans << '\n';
f.close();
g.close();
return 0;
}