Pagini recente » Cod sursa (job #2357580) | Cod sursa (job #2953885) | Cod sursa (job #2394226) | Cod sursa (job #2542080) | Cod sursa (job #1947591)
#include <bits/stdc++.h>
#define x first
#define y second
#define MAXN 50001
using namespace std;
vector < pair<int, int> > v[4];
pair <int, int> start;
int k, path[MAXN], lg[MAXN];
int binarySearch(int value)
{
int ans = 0, step;
if(!k) return 0;
for(step=(1<<lg[k]); step>=1; step>>=1)
if(ans + step <= k && path[ans + step] > value)
ans += step;
if(ans == k)
return 0;
return ans+1;
}
int checkWays(int index)
{
int pos, i;
sort(v[index].begin(), v[index].end());
k = 0;
for(i=0; i<v[index].size(); ++i) {
pos = binarySearch(v[index][i].y);
if(pos)
path[pos] = v[index][i].y;
else path[++k] = v[index][i].y;
}
return k;
}
int main()
{
freopen("pachete.in", "r", stdin);
freopen("pachete.out", "w", stdout);
int i, n, ox, oy, answer = 0;
pair <int, int> point;
scanf("%d%d%d", &n, &start.x, &start.y);
for(i=1; i<=n; ++i) {
scanf("%d%d", &point.x, &point.y);
if(point.x < start.x) {
if(point.y >= start.y) {
ox = abs(start.x - point.x);
oy = abs(point.y - start.y);
v[1].push_back({ox, oy});
}else{
ox = abs(start.x - point.x);
oy = abs(start.y - point.y);
v[2].push_back({ox, oy});
}
}
else {
if(point.y >= start.y) {
ox = abs(point.x - start.x);
oy = abs(point.y - start.y);
v[0].push_back({ox, oy});
}else{
ox = abs(point.x - start.x);
oy = abs(start.y - point.y);
v[3].push_back({ox, oy});
}
}
}
lg[2] = 1;
for(i=3; i<=n; ++i)
lg[i] = lg[i/2] + 1;
for(i=0; i<4; ++i)
answer += checkWays(i);
printf("%d", answer);
return 0;
}