Pagini recente » Cod sursa (job #2172090) | Cod sursa (job #2988431) | Cod sursa (job #1904957) | Cod sursa (job #1625538) | Cod sursa (job #19230)
Cod sursa(job #19230)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define MAXN 50005
int N;
vector< pair<int, int> > x[4];
set< pair<int, int> > Min;
vector<int> y;
int NR = 0;
void solve( vector< pair<int, int> > &x )
{
if (x.size() == 0)
return;
Min.clear();
y.clear();
y.push_back( x[0].second );
Min.insert( make_pair( y[0], 0 ) );
for (int i = 1; i < (int)x.size(); i++)
{
int M = (*Min.begin()).first, p = (*Min.begin()).second;
if (x[i].second < M)
{
y.push_back( x[i].second );
Min.insert( make_pair( y.back(), y.size() - 1 ) );
}
else
{
Min.erase( Min.find( make_pair( y[p], p ) ) );
y[p] = x[i].second;
Min.insert( make_pair( y[p], p ) );
}
}
NR += y.size();
}
int main()
{
freopen("pachete.in", "rt", stdin);
freopen("pachete.out", "wt", stdout);
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
int a, b;
scanf("%d %d", &a, &b);
x[ ((a < 0) << 1) | (b < 0) ].push_back( make_pair( abs(a), abs(b)) );
}
for (int i = 0; i < 4; i++)
{
sort(x[i].begin(), x[i].end());
x[i].resize( unique(x[i].begin(), x[i].end()) - x[i].begin() );
solve( x[i] );
}
printf("%d\n", NR);
return 0;
}