/**
/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
const int inf = 2e9;
struct point
{
int x, y;
} p[maxn];
int n, used[maxn], dir[maxn];
/**
directions:
0 - north
1 - east
2 - south
3 - west
*/
struct collision
{
int idx1, idx2, tp;
collision(int _idx1, int _idx2, int _tp)
{
idx1 = _idx1;
idx2 = _idx2;
tp = _tp;
}
bool operator < (const collision &c) const
{
if (tp != c.tp)
return tp < c.tp;
if (min(idx2, idx1) != min(c.idx1, c.idx2))
return min(idx2, idx1) < min(c.idx1, c.idx2);
return max(idx1, idx2 ) < max(c.idx1, c.idx2);
}
};
bool cmp(collision c1, collision c2)
{
return c1.tp < c2.tp;
}
unordered_map < int, set < pair < int, int > > > mdig[4], fdig[4];
unordered_map < int, set < pair < int, int > > > mrow[4], fcol[4];
set < collision > event;
int get_collision_time(int i, int j)
{
if (p[i].x == p[j].x)
{
return abs(p[j].y - p[i].y);
}
if (p[i].y == p[j].y)
{
return abs(p[i].x - p[j].x);
}
return 2 * abs(p[i].x - p[j].x);
}
void get_next_collsion(int id)
{
int md = p[id].y - p[id].x;
int fd = p[id].x + p[id].y;
collision nxt(0,0, inf);
set < pair < int, int > > :: iterator it;
int dist = (used[id] + 1) / 2;
if (dir[id] == 0)
{
it = mdig[3][md].lower_bound({p[id].x + dist, -inf});
if (it != mdig[3][md].end())
{
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
it = fdig[1][fd].lower_bound({p[id].x - dist, inf});
if (it != fdig[1][fd].begin())
{
it = prev(it);
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
}
if (dir[id] == 1)
{
it = mdig[2][md].lower_bound({p[id].x + dist, - inf});
if (it != mdig[2][md].end())
{
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
it = fdig[0][fd].lower_bound({p[id].x + dist, -inf});
if (it != fdig[0][fd].end())
{
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
}
if (dir[id] == 2)
{
it = mdig[1][md].lower_bound({p[id].x - dist, inf});
if (it != mdig[1][md].begin())
{
it = prev(it);
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
it = fdig[3][fd].lower_bound({p[id].x + dist, -inf});
if (it != fdig[3][fd].end())
{
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
}
if (dir[id] == 3)
{
it = mdig[0][md].lower_bound({p[id].x - dist, inf});
if (it != mdig[0][md].begin())
{
it = prev(it);
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
it = fdig[2][fd].lower_bound({p[id].x - dist, inf});
if (it != fdig[2][fd].begin())
{
it = prev(it);
collision cur(id, it -> second, get_collision_time(id, it -> second));
nxt = min(nxt, cur);
}
}
///cout << "next collision " << id << " " << nxt.idx2 << " " << nxt.tp << endl;
if (nxt.tp != inf)
event.insert(nxt);
}
void add_point(int i)
{
mdig[dir[i]][p[i].y - p[i].x].insert({p[i].x, i});
fdig[dir[i]][p[i].y + p[i].x].insert({p[i].x, i});
mrow[dir[i]][p[i].y].insert({p[i].x, i});
mcol[dir[i]][p[i].x].insert({p[i].y, i});
}
void rem_point(int i)
{
mdig[dir[i]][p[i].y - p[i].x].erase({p[i].x, i});
fdig[dir[i]][p[i].y + p[i].x].erase({p[i].x, i});
mrow[dir[i]][p[i].y].erase({p[i].x, i});
mcol[dir[i]][p[i].x].erase({p[i].y, i});
}
int simulate()
{
for (int i = 0; i < 4; i ++)
{
mdig[i].clear();
fdig[i].clear();
mrow[i].clear();
fcol[i].clear();
}
event.clear();
dir[1] = 1;
for (int i = 2; i <= n; i ++)
{
if (p[i].x > 0 && p[i].y > 0)
{
if (p[i].x > p[i].y)
dir[i] = 3;
else
dir[i] = 2;
}
else if (p[i].x > 0 && p[i].y < 0)
{
if (p[i].x > abs(p[i].y))
dir[i] = 3;
else
dir[i] = 0;
}
else if (p[i].x < 0 && p[i].y > 0)
{
if (abs(p[i].x) < p[i].y)
dir[i] = 2;
else
dir[i] = 1;
}
else if (p[i].x < 0 && p[i].y < 0)
{
if (abs(p[i].x) < abs(p[i].y))
dir[i] = 0;
else
dir[i] = 1;
}
else
{
if (p[i].x == 0)
{
if (p[i].y > 0)
dir[i] = 2;
else
dir[i] = 0;
}
else
{
if (p[i].x > 0)
dir[i] = 3;
else
dir[i] = 1;
}
}
add_point(i);
}
for (int i = 1; i <= n; i ++)
{
used[i] = -1;
}
used[1] = 0;
get_next_collsion(1);
int ans = 1;
while(!event.empty())
{
collision cur = *event.begin();
event.erase(event.begin());
if (used[cur.idx1] != -1 && used[cur.idx2] != -1)
{
get_next_collsion(cur.idx1);
continue;
}
///cout << "collision " << cur.idx1 << " " << cur.idx2 << " " << cur.tp << endl;
used[cur.idx2] = cur.tp;
ans ++;
rem_point(cur.idx2);
get_next_collsion(cur.idx1);
get_next_collsion(cur.idx2);
}
///cout << ans << endl;
///exit(0);
return ans;
}
void perform90()
{
for (int i = 1; i <= n; i ++)
{
int nx = p[i].y, ny = - p[i].x;
p[i].x = nx;
p[i].y = ny;
}
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> p[i].x >> p[i].y;
if (i != 1)
{
p[i].x -= p[1].x;
p[i].y -= p[1].y;
}
}
p[1].x = p[1].y = 0;
int ans = 0;
/**perform90();
perform90();
perform90();
simulate();*/
for (int d = 0; d < 4; d ++)
{
ans = max(ans, simulate());
perform90();
}
cout << ans << endl;
}
int main()
{
speed();
solve();
return 0;
}
/**
15
107 139
114 146
105 137
88 120
130 130
112 148
123 123
93 93
128 128
113 113
106 140
99 147
146 100
108 142
115 135
7
64 52
68 56
65 53
62 62
44 44
60 60
59 59
3
0 0
1 1
-1 3
15
0 0
7 7
-2 -2
-19 -19
23 -9
5 9
16 -16
-14 -46
21 -11
6 -26
-1 1
-8 8
39 -39
1 3
8 -4
collision 1 3 4
collision 2 3 18
collision 1 7 32
collision 2 5 32
collision 11 7 34
collision 5 10 34
collision 6 5 36
collision 1 4 38
collision 12 7 48
collision 7 8 60
collision 9 8 70
collision 1 13 78
*/
Compilation message
fever.cpp:2:1: warning: "/*" within comment [-Wcomment]
2 | /**
|
fever.cpp: In function 'void add_point(int)':
fever.cpp:174:9: error: 'mcol' was not declared in this scope; did you mean 'fcol'?
174 | mcol[dir[i]][p[i].x].insert({p[i].y, i});
| ^~~~
| fcol
fever.cpp: In function 'void rem_point(int)':
fever.cpp:182:9: error: 'mcol' was not declared in this scope; did you mean 'fcol'?
182 | mcol[dir[i]][p[i].x].erase({p[i].y, i});
| ^~~~
| fcol
