Pagini recente » Cod sursa (job #2984152) | Cod sursa (job #1422812) | Cod sursa (job #2433280) | Cod sursa (job #376895) | Cod sursa (job #1675788)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
const int MAXN = 50005;
struct Point{
int x, y;
};
int N;
Point s, p;
vector<Point> P[4];
int D[4][MAXN];
int nrp[4];
int nd[4];
int BinarySearch( int k, int x );
bool Comp( const Point& x, const Point& y )
{
if ( x.x < y.x || ( x.x == y.x && x.y < y.y ) )
return true;
return false;
}
int main()
{
int i, j;
int poz;
fin >> N;
fin >> s.x >> s.y;
// P[0].resize(N + 1);
// P[1].resize(N + 1);
// P[2].resize(N + 1);
// P[3].resize(N + 1);
for ( i = 1; i <= N; i++ )
{
fin >> p.x >> p.y;
p.x -= s.x, p.y -= s.y;
if ( p.x < 0 && p.y < 0 )
{
p.x = -p.x, p.y = -p.y;
P[0].push_back( p );
continue;
}
if ( p.x < 0 && p.y >= 0 )
{
p.x = -p.x;
P[1].push_back( p );
continue;
}
if ( p.x >= 0 && p.y < 0 )
{
p.y = -p.y;
P[2].push_back( p );
continue;
}
if ( p.x >= 0 && p.y >= 0 )
{
P[3].push_back( p );
continue;
}
}
for ( i = 0; i < 4; i++ )
if ( P[i].size() > 0 )
{
nrp[i] = P[i].size();
sort( P[i].begin(), P[i].end(), Comp );
D[i][++nd[i]] = P[i][0].y;
for ( j = 1; j < nrp[i]; j++ )
{
poz = BinarySearch(i, P[i][j].y);
if ( D[i][poz] != 0 )
D[i][poz] = P[i][j].y;
else
D[i][++nd[i]] = P[i][j].y;
}
}
fout << nd[0] + nd[1] + nd[2] + nd[3] << '\n';
fin.close();
fout.close();
return 0;
}
int BinarySearch( int k, int x )
{
int st = 1, dr = nd[k], mid, rez = nd[k] + 1;
while ( st <= dr )
{
mid = ( st + dr ) / 2;
if ( D[k][mid] <= x )
{
rez = mid;
dr = mid - 1;
}
else
st = mid + 1;
}
return rez;
}