#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
// returns number of elements strictly smaller than v in vec
template<class T>
int bins(const vector<T>& vec, T v) {
int low = 0;
int high = vec.size();
while(low != high) {
int mid = (low + high) >> 1;
if (vec[mid] < v) low = mid + 1;
else high = mid;
}
return low;
}
// Struct for priority queue operations on index set [0, n-1]
// push(i, v) overwrites value at position i if one already exists
// decKey is faster but requires that the new key is smaller than the old one
struct Prique {
const ll INF = (ll)1e18;
vector<pair<ll, int>> data;
const int n;
Prique(int siz) : n(siz), data(2*siz, {INF, -1}) { data[0] = {-INF, -1}; }
bool empty() const { return data[1].second >= INF; }
pair<ll, int> top() const { return data[1]; }
void push(int i, ll v) {
data[i+n] = {v, (v >= INF ? -1 : i)};
for (i += n; i > 1; i >>= 1) data[i>>1] = min(data[i], data[i^1]);
}
void decKey(int i, ll v) {
for (int j = i+n; data[j].first > v; j >>= 1) data[j] = {v, i};
}
pair<ll, int> pop() {
auto res = data[1];
push(res.second, INF);
return res;
}
};
// Segment tree for range minimum and range capping
class SegTree {
private:
const ll INF = (ll)1e18;
vector<ll> mn, cap, base;
int h = 1;
void apply(int i, ll v) {
cap[i] = min(cap[i], v);
mn[i] = min(mn[i], base[i] + cap[i]);
}
void push(int i) {
apply(2*i, cap[i]);
apply(2*i+1, cap[i]);
cap[i] = INF;
}
void recApply(int a, int b, ll v, int i, int ia, int ib) {
if (ib <= a || b <= ia) return;
if (a <= ia && ib <= b) {
apply(i, v);
} else {
push(i);
int im = (ia + ib) >> 1;
recApply(a, b, v, 2*i, ia, im);
recApply(a, b, v, 2*i+1, im, ib);
mn[i] = min(mn[2*i], mn[2*i+1]);
}
}
public:
SegTree(int n) {
while(h < n) h *= 2;
mn.resize(2*h, 2*INF); base.resize(2*h, INF); cap.resize(2*h, INF);
}
void rangeCap(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
ll getMinVal() { return mn[1]; }
void setBase(int i, ll v) {
i += h;
base[i] = v;
mn[i] = base[i] + cap[i];
for (i >>= 1; i > 0; i >>= 1) {
base[i] = min(base[2*i], base[2*i+1]);
mn[i] = min(cap[i] + base[i], min(mn[2*i], mn[2*i+1]));
}
}
pair<ll, int> getMin() {
int i = 1;
ll res = mn[1];
while(i < h) {
push(i);
if (mn[2*i] == mn[i]) i = 2*i;
else i = 2*i+1;
}
return {res, i - h};
}
};
pair<int, int> rotate(pair<int, int> dir) {
return {dir.second, -dir.first};
}
int sign(ll v) {
return (v < 0 ? -1 : v > 0);
}
int solve(const vector<pair<ll, ll>>& pts) {
int n = pts.size();
vector<int> dir(n); // RIGHT DOWN LEFT UP
dir[0] = 0;
for (int i = 1; i < n; ++i) {
ll dx = pts[i].first, dy = pts[i].second;
if (abs(dx) > abs(dy)) {
if (dx < 0) dir[i] = 0;
else dir[i] = 2;
} else if (abs(dy) > abs(dx) || dx > 0) {
if (dy < 0) dir[i] = 3;
else dir[i] = 1;
} else {
dir[i] = 0;
}
}
vector<pair<int, int>> diffs(8);
diffs[0] = {1, 0};
diffs[1] = {1, -1};
diffs[2] = {0, -1};
diffs[3] = {-1, -1};
diffs[4] = {-1, 0};
diffs[5] = {-1, 1};
diffs[6] = {0, 1};
diffs[7] = {1, 1};
vector<vector<array<ll, 4>>> ords(8);
for (int i = 0; i < n; ++i) {
int dx = sign(diffs[2*dir[i]].first);
int dy = sign(diffs[2*dir[i]].second);
for (int j = 0; j < 8; ++j) {
if (sign(diffs[j].first) != -dx && sign(diffs[j].second) != -dy) continue;
array<ll, 4> off;
off[0] = dir[i];
pair<int, int> tar = diffs[j];
pair<int, int> ortho = rotate(tar);
off[1] = ortho.first * pts[i].first + ortho.second * pts[i].second;
off[2] = tar.first * pts[i].first + tar.second * pts[i].second;
off[3] = i;
ords[j].push_back(off);
}
}
for (int j = 0; j < 8; ++j) sort(ords[j].begin(), ords[j].end());
vector<SegTree> segs;
for (int j = 0; j < 8; ++j) {
segs.emplace_back(ords[j].size());
for (int i = 0; i < ords[j].size(); ++i) {
if (ords[j][i][3] == 0) {
segs[j].setBase(i, 0);
segs[j].rangeCap(i, i, 0);
} else {
segs[j].setBase(i, ords[j][i][2]);
}
}
}
Prique pq(8);
for (int j = 0; j < 8; ++j) pq.decKey(j, segs[j].getMin().first);
vector<ll> times(n, INF);
for (int j = pq.pop().second; j != -1; j = pq.pop().second) {
auto opt = segs[j].getMin();
segs[j].setBase(opt.second, INF);
pq.decKey(j, segs[j].getMinVal());
int i = ords[j][opt.second][3];
ll t = opt.first;
if (t >= INF / 2) break;
if (t >= times[i]) continue;
times[i] = t;
int d = dir[i];
for (int j2 = 0; j2 < 8; ++j2) {
array<ll, 4> ind;
// Desired direction
if (j2 == (2*d+7) % 8) ind[0] = (d+1) % 4;
else if (j2 == 2*d) ind[0] = (d + 2) % 4;
else if (j2 == (2*d+1) % 8) ind[0] = (d+3) % 4;
else continue;
// Desired line
pair<int, int> ortho = rotate(diffs[j2]);
ind[1] = ortho.first * pts[i].first + ortho.second * pts[i].second;
// Desired min coordinate
ll base = diffs[j2].first * pts[i].first + diffs[j2].second * pts[i].second;
ind[2] = t + base;
// OK indices
ind[3] = -1;
int i0 = bins(ords[j2], ind);
ind[2] = INF;
int i1 = bins(ords[j2], ind);
segs[j2].rangeCap(i0, i1 - 1, -base);
pq.decKey(j2, segs[j2].getMinVal());
}
}
int res = 0;
for (ll& v : times) res += (v < INF);
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<pair<ll, ll>> pts(n);
for (int i = 0; i < n; ++i) {
int y, x;
cin >> y >> x;
pts[i] = {y, x};
}
for (int i = 1; i < n; ++i) {
pts[i].first -= pts[0].first;
pts[i].second -= pts[0].second;
}
pts[0] = {0, 0};
// Decide direction person 1 goes to
int res = 0;
res = max(res, solve(pts)); // Right
for (auto& pr : pts) pr.first = -pr.first;
res = max(res, solve(pts)); // Left
for (auto& pr : pts) swap(pr.first, pr.second);
res = max(res, solve(pts)); // Up
for (auto& pr : pts) pr.first = -pr.first;
res = max(res, solve(pts)); // Down
cout << res << '\n';
}
