//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define x first
#define y second
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1e9 + 7;
auto LB(vector<pii> v, pii p) {
return lower_bound(v.begin(), v.end(), p);
}
auto UB(vector<pii> v, pii p) {
return lower_bound(v.begin(), v.end(), p);
}
pii a[maxn];
vector<pii> horz[4][maxn], vert[4][maxn], ru[4][maxn], rd[4][maxn];
unordered_map<ll, int> mp;
ll h(pii p) {
return (ll)inf * p.x + p.y;
}
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int movru[4][2] = {{1, 1}, {1, 1}, {-1, -1}, {-1, -1}};
int movrd[4][2] = {{1, -1}, {-1, 1}, {-1, 1}, {1, -1}};
int mind[maxn][3], di[maxn];
bool vis[maxn];
int hi[maxn], vi[maxn], rui[maxn], rdi[maxn];
int main() {
io
int n;
cin >> n;
{
vector<int> h, v, u, d;
for (int i = 0;i < n;i++) {
cin >> a[i].x >> a[i].y;
a[i].x *= 2, a[i].y *= 2;
h.push_back(a[i].y);
v.push_back(a[i].x);
u.push_back(a[i].x - a[i].y);
d.push_back(a[i].x + a[i].y);
}
auto rs = [&] (vector<int> &ve) {
sort(ve.begin(), ve.end());
ve.resize(int(unique(ve.begin(), ve.end()) - ve.begin()));
};
rs(h), rs(v), rs(u), rs(d);
for (int i = 0;i < n;i++) {
hi[i] = lower_bound(h.begin(), h.end(), a[i].y) - h.begin();
vi[i] = lower_bound(v.begin(), v.end(), a[i].x) - v.begin();
rui[i] = lower_bound(u.begin(), u.end(), a[i].x - a[i].y) - u.begin();
rdi[i] = lower_bound(d.begin(), d.end(), a[i].x + a[i].y) - d.begin();
}
}
for (int i = 0;i < n;i++) mp[h(a[i])] = i;
int ans = 0;
for (int init_d = 0;init_d < 4;init_d++) {
for (int i = 0;i < 4;i++) {
for (int j = 0;j < maxn;j++) {
horz[i][j].clear(), vert[i][j].clear(), ru[i][j].clear(), rd[i][j].clear();
}
}
for (int i = 0;i < n;i++) {
mind[i][0] = mind[i][1] = mind[i][2] = inf;
vis[i] = 0;
if (i == 0) continue;
int dx = a[i].x - a[0].x, dy = a[i].y - a[0].y;
if (abs(dx) > abs(dy)) {
di[i] = dx > 0 ? 2 : 0;
} else if (abs(dx) < abs(dy)) {
di[i] = dy > 0 ? 3 : 1;
} else {
pii tmp = {dx, dy};
for (int j = 0;j < 4 - init_d;j++) tmp = {-tmp.y, tmp.x};
if (tmp.x > 0) di[i] = tmp.y > 0 ? 3 : 1;
else di[i] = 0;
di[i] = (di[i] + init_d)%4;
}
if (di[i] % 2) {
vert[di[i]][vi[i]].push_back(a[i]);
} else {
horz[di[i]][hi[i]].push_back(a[i]);
}
ru[di[i]][rui[i]].push_back(a[i]);
rd[di[i]][rdi[i]].push_back(a[i]);
}
for (int i = 0;i < 4;i++) {
for (int j = 0;j < maxn;j++) {
sort(horz[i][j].begin(), horz[i][j].end());
sort(vert[i][j].begin(), vert[i][j].end());
sort(ru[i][j].begin(), ru[i][j].end());
sort(rd[i][j].begin(), rd[i][j].end());
}
}
mind[0][0] = 0;
di[0] = init_d;
auto col = [&] (int i, int j) {
int dx = a[j].x - a[i].x, dy = a[j].y - a[i].y;
int divx = mov[di[i]][0] - mov[di[j]][0], divy = mov[di[i]][1] - mov[di[j]][1];
if (dx && divx == 0) return -1;
if (dy && divy == 0) return -1;
if (dx == 0) {
if (abs(di[i] - di[j]) == 2) return dy / divy;
return -1;
}
if (dy == 0) {
if (abs(di[i] - di[j]) == 2) return dx / divx;
return -1;
}
if (dx * divy != dy * divx) return -1;
return dx / divx;
};
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push({0, 0});
pii cur;
int id, prv = 0, ti;
auto relax = [&](pii p, int d, int val) {
int ind = mp[h(p)];
if (val >= ti && val < mind[ind][d]) {
mind[ind][d] = val;
pq.push({val, ind * 3 + d});
}
};
auto upd = [&] (vector<pii> &se, auto it, int d, bool type) {
pii p;
if (type == 0) {
if (it != se.begin()) {
p = *prev(it);
} else {
return;
}
} else {
if (it != se.end()) {
p = *it;
} else {
return;
}
}
relax(p, d, col(id, mp[h(p)]));
};
auto to = [&] (vector<pii> &se, bool type) { //0:prev, 1:next
auto it = LB(se, cur);
pii q;
if (type && next(it) != se.end()) {
q = *next(it);
} else if (type == 0 && it != se.begin()) {
q = *prev(it);
}
int val = (abs(q.y - cur.y) + abs(q.x - cur.x)) / 2;
relax(q, prv, ti + val);
};
while (pq.size()) {
id = pq.top().ss / 3, prv = pq.top().ss % 3;
ti = pq.top().ff;
pq.pop();
if (ti != mind[id][prv]) continue;
debug("cur", id, prv, ti, di[id]);
cur = a[id];
vis[id] = 1;
int dir = di[id];
pii pos = {cur.x + mov[dir][0] * 2 * ti, cur.y + mov[dir][1] * 2 * ti};
if (dir % 2 == 0) {
auto se = horz[(dir+2)%4][hi[id]];
if (dir == 0) upd(se, LB(se, pos), 0, 1);
else upd(se, UB(se, pos), 0, 0);
} else {
auto se = vert[(dir+2)%4][vi[id]];
if (dir == 1) upd(se, LB(se, pos), 0, 1);
else upd(se, UB(se, pos), 0, 0);
}
pos = {cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti};
auto se = ru[(3 - dir)][rui[id]];
if (dir < 2) upd(se, LB(se, pos), 1, 1);
else upd(se, UB(se, pos), 1, 0);
pos = {cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti};
se = rd[(dir < 2 ? 1 - dir : 5 - dir)][rdi[id]];
if (dir == 0 || dir == 3) upd(se, LB(se, pos), 2, 1);
else upd(se, UB(se, pos), 2, 0);
if (id == 0) continue;
if (prv == 0) {
if (dir % 2 == 0) to(horz[dir][hi[id]], dir == 2);
else to(vert[dir][vi[id]], dir == 3);
} else if (prv == 1) {
to(ru[dir][rui[id]], dir >= 2);
} else {
to(rd[dir][rdi[id]], dir == 1 || dir == 2);
}
}
int cnt = 0;
for (int i = 0;i < n;i++) {
if (vis[i]) cnt++;
}
ans = max(ans, cnt);
}
cout << ans << "\n";
}
Compilation message
fever.cpp: In function 'int main()':
fever.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
fever.cpp:178:4: note: in expansion of macro 'debug'
178 | debug("cur", id, prv, ti, di[id]);
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37928 KB |
Output is correct |
| 3 |
Runtime error |
48 ms |
76648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37928 KB |
Output is correct |
| 3 |
Runtime error |
48 ms |
76648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
50 ms |
76660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37928 KB |
Output is correct |
| 3 |
Runtime error |
48 ms |
76648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37928 KB |
Output is correct |
| 3 |
Runtime error |
48 ms |
76648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37928 KB |
Output is correct |
| 3 |
Runtime error |
48 ms |
76648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
32 ms |
37928 KB |
Output is correct |
| 3 |
Runtime error |
48 ms |
76648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
