#include <bits/stdc++.h>
using namespace std;
#define int int64_t
struct point {
int x, y;
};
enum dir {
RIGHT,
LEFT,
UP,
DOWN
};
enum linetype {
NORMAL,
X_PLUS_Y,
X_MINUS_Y,
X_EQUALS_CONST,
Y_EQUALS_CONST
};
enum onwhat {
ON_X,
ON_Y
};
struct maptype {
linetype linetyp;
onwhat onwha;
dir direction;
bool operator<(const maptype &r) const {
if (linetyp != r.linetyp) {
return linetyp < r.linetyp;
}
if (onwha != r.onwha) {
return onwha < r.onwha;
}
return direction < r.direction;
}
};
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
int solve(int n, vector<point> a) {
vector<dir> dirs = {RIGHT};
for (int i = 1; i < n; ++i) {
auto [x, y] = a[i];
if (x >= 0 && y >= 0) {
dirs.push_back(y < x ? LEFT : DOWN);
} else if (x >= 0 && y < 0) {
dirs.push_back(x > -y ? LEFT : UP);
} else if (x < 0 && y >= 0) {
dirs.push_back(y > -x ? DOWN : RIGHT);
} else {
dirs.push_back(-y > -x ? UP : RIGHT);
}
}
map<maptype, map<int, set<pair<int, int>>>> mps;
for (int i = 0; i < n; ++i) {
auto [x, y] = a[i];
mps[{X_MINUS_Y, ON_X, dirs[i]}][x - y].insert({x, i});
mps[{X_MINUS_Y, ON_Y, dirs[i]}][x - y].insert({y, i});
mps[{X_PLUS_Y, ON_X, dirs[i]}][x + y].insert({x, i});
mps[{X_PLUS_Y, ON_Y, dirs[i]}][x + y].insert({y, i});
mps[{X_EQUALS_CONST, ON_Y, dirs[i]}][x].insert({y, i});
mps[{Y_EQUALS_CONST, ON_X, dirs[i]}][y].insert({x, i});
}
min_heap<pair<int, pair<int, pair<linetype, dir>>>> pq;
pq.push({0, {0, {NORMAL, LEFT}}});
vector vis(n, vector<int>(9));
auto flat = [&](pair<linetype, dir> p) -> int {
if (p.first == NORMAL) {
return 0;
}
if (p.second == LEFT) {
return int(p.first);
}
return int(p.first) + 4;
};
while (!pq.empty()) {
auto [t, p] = pq.top();
auto [i, mode] = p;
pq.pop();
if (vis[i][flat(mode)]) {
continue;
}
vis[i][flat(mode)] = 1;
auto [x, y] = a[i];
if (mode.first != NORMAL) {
pq.push({t, {i, {NORMAL, LEFT}}});
auto *st = &mps[{X_MINUS_Y, ON_X, dirs[i]}][x - y];
if (mode.first == X_PLUS_Y) {
st = &mps[{X_PLUS_Y, ON_X, dirs[i]}][x + y];
}
if (mode.first == X_EQUALS_CONST) {
st = &mps[{X_EQUALS_CONST, ON_Y, dirs[i]}][x];
}
if (mode.first == Y_EQUALS_CONST) {
st = &mps[{Y_EQUALS_CONST, ON_X, dirs[i]}][y];
}
int qty = (mode.first == X_EQUALS_CONST ? y : x);
int cost_per_unit = (mode.first == X_EQUALS_CONST || mode.first == Y_EQUALS_CONST) ? 1 : 2;
auto it = st->find({qty, i});
if (mode.second == RIGHT && it != prev(st->end())) {
pq.push({t + cost_per_unit * (next(it)->first - qty), {next(it)->second, mode}});
}
if (mode.second == LEFT && it != st->begin()) {
pq.push({t + cost_per_unit * (qty - prev(it)->first), {prev(it)->second, mode}});
}
continue;
}
auto add = [&](int dist2, int j, linetype z, dir direc) {
if (dist2 >= t) {
pq.push({dist2, {j, {z, direc}}});
}
};
if (dirs[i] == RIGHT) {
// x-y = const, their y >= our y, actual time = dy, doubled time = 2*dy
auto &st1 = mps[{X_MINUS_Y, ON_Y, DOWN}][x - y];
if (auto it = st1.lower_bound({y + t / 2, -1}); it != st1.end()) {
add(2 * (it->first - y), it->second, X_MINUS_Y, RIGHT);
}
// x+y = const, their y <= our y, actual time = dy, doubled time = 2*dy
auto &st2 = mps[{X_PLUS_Y, ON_Y, UP}][x + y];
if (auto it = st2.upper_bound({y - t / 2, n}); it != st2.begin()) {
--it;
add(2 * (y - it->first), it->second, X_PLUS_Y, RIGHT);
}
// y = const, their x >= our x, actual time = dx/2, doubled time = dx
auto &st3 = mps[{Y_EQUALS_CONST, ON_X, LEFT}][y];
if (auto it = st3.lower_bound({x + t, -1}); it != st3.end()) {
add(it->first - x, it->second, Y_EQUALS_CONST, RIGHT);
}
} else if (dirs[i] == DOWN) {
// x-y = const, their x <= our x
auto &st1 = mps[{X_MINUS_Y, ON_X, RIGHT}][x - y];
if (auto it = st1.upper_bound({x - t / 2, n}); it != st1.begin()) {
--it;
add(2 * (x - it->first), it->second, X_MINUS_Y, LEFT);
}
// x+y = const, their x >= our x
auto &st2 = mps[{X_PLUS_Y, ON_X, LEFT}][x + y];
if (auto it = st2.lower_bound({x + t / 2, -1}); it != st2.end()) {
add(2 * (it->first - x), it->second, X_PLUS_Y, RIGHT);
}
// x = const, their y <= our y, actual time = dy/2, doubled time = dy
auto &st3 = mps[{X_EQUALS_CONST, ON_Y, UP}][x];
if (auto it = st3.upper_bound({y - t, n}); it != st3.begin()) {
--it;
add(y - it->first, it->second, X_EQUALS_CONST, LEFT);
}
} else if (dirs[i] == LEFT) {
// x+y = const, their y >= our y
auto &st1 = mps[{X_PLUS_Y, ON_Y, DOWN}][x + y];
if (auto it = st1.lower_bound({y + t / 2, -1}); it != st1.end()) {
add(2 * (it->first - y), it->second, X_PLUS_Y, LEFT);
}
// x-y = const, their y <= our y
auto &st2 = mps[{X_MINUS_Y, ON_Y, UP}][x - y];
if (auto it = st2.upper_bound({y - t / 2, n}); it != st2.begin()) {
--it;
add(2 * (y - it->first), it->second, X_MINUS_Y, LEFT);
}
// y = const, their x <= our x
auto &st3 = mps[{Y_EQUALS_CONST, ON_X, RIGHT}][y];
if (auto it = st3.upper_bound({x - t, n}); it != st3.begin()) {
--it;
add(x - it->first, it->second, Y_EQUALS_CONST, LEFT);
}
} else { // UP
// x-y = const, their x >= our x
auto &st1 = mps[{X_MINUS_Y, ON_X, LEFT}][x - y];
if (auto it = st1.lower_bound({x + t / 2, -1}); it != st1.end()) {
add(2 * (it->first - x), it->second, X_MINUS_Y, RIGHT);
}
// x+y = const, their x <= our x
auto &st2 = mps[{X_PLUS_Y, ON_X, RIGHT}][x + y];
if (auto it = st2.upper_bound({x - t / 2, n}); it != st2.begin()) {
--it;
add(2 * (x - it->first), it->second, X_PLUS_Y, LEFT);
}
// x = const, their y >= our y
auto &st3 = mps[{X_EQUALS_CONST, ON_Y, DOWN}][x];
if (auto it = st3.lower_bound({y + t, -1}); it != st3.end()) {
add(it->first - y, it->second, X_EQUALS_CONST, RIGHT);
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += vis[i][NORMAL];
}
return ans;
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<point> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
for (auto &[x, y] : a | views::drop(1)) {
x -= a[0].x, y -= a[0].y;
}
a[0] = {0, 0};
auto rotate = [&]() {
for (auto &[x, y] : a) {
int nx = y, ny = -x;
x = nx, y = ny;
}
};
int ans = solve(n, a);
rotate();
ans = max(ans, solve(n, a));
rotate();
ans = max(ans, solve(n, a));
rotate();
cout << max(ans, solve(n, a)) << '\n';
}
