Pagini recente » Cod sursa (job #3040849) | Cod sursa (job #3282883) | Rating Ciocoiu Vlad (vlad082002) | Scrie articole | Cod sursa (job #3222813)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
ifstream in("pachete.in");
ofstream out("pachete.out");
int n, ans, cnt;
int ox, oy;
vector<pair<int, int>> v1;
vector<pair<int, int>> v2;
vector<pair<int, int>> v3;
vector<pair<int, int>> v4;
vector<int> vec[50005];
int cauta(int x)
{
int st = 1;
int dr = cnt;
int ans = -1;
int mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(vec[mij][vec[mij].size() - 1] <= x)
{
ans = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
return ans;
}
signed main()
{
in>>n;
in>>ox>>oy;
int x, y;
for(int i = 1; i<=n; i++)
{
in>>x>>y;
if(x >= ox && y >= oy)
{
v1.push_back({x, y});
}
else if(x < ox && y >= oy)
{
v2.push_back({x * (-1), y});
}
else if(x <= ox && y < oy)
{
v3.push_back({x * (-1), y * (-1)});
}
else
{
v4.push_back({x, y * (-1)});
}
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
sort(v3.begin(), v3.end());
sort(v4.begin(), v4.end());
for(int i = 0; i<v1.size(); i++)
{
if(i == 0)
{
cnt++;
vec[cnt].push_back(v1[i].second);
}
else
{
int poz = cauta(v1[i].second);
if(poz == -1)
{
cnt++;
vec[cnt].push_back(v1[i].second);
}
else
{
vec[poz].push_back(v1[i].second);
}
}
}
ans += cnt;
//out<<cnt<<'\n';
for(int i = 1; i<=cnt; i++)
{
vec[i].clear();
}
cnt = 0;
for(int i = 0; i<v2.size(); i++)
{
if(i == 0)
{
cnt++;
vec[cnt].push_back(v2[i].second);
}
else
{
int poz = cauta(v2[i].second);
if(poz == -1)
{
cnt++;
vec[cnt].push_back(v2[i].second);
}
else
{
vec[poz].push_back(v2[i].second);
}
}
}
ans += cnt;
//out<<cnt<<'\n';
for(int i = 1; i<=cnt; i++)
{
vec[i].clear();
}
cnt = 0;
for(int i = 0; i<v3.size(); i++)
{
if(i == 0)
{
cnt++;
vec[cnt].push_back(v3[i].second);
}
else
{
int poz = cauta(v3[i].second);
if(poz == -1)
{
cnt++;
vec[cnt].push_back(v3[i].second);
}
else
{
vec[poz].push_back(v3[i].second);
}
}
}
ans += cnt;
//out<<cnt<<'\n';
for(int i = 1; i<=cnt; i++)
{
vec[i].clear();
}
cnt = 0;
for(int i = 0; i<v4.size(); i++)
{
if(i == 0)
{
cnt++;
vec[cnt].push_back(v4[i].second);
}
else
{
int poz = cauta(v4[i].second);
if(poz == -1)
{
cnt++;
vec[cnt].push_back(v4[i].second);
}
else
{
vec[poz].push_back(v4[i].second);
}
}
}
ans += cnt;
//out<<cnt<<'\n';
out<<ans;
return 0;
}