This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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;
struct pnt{
int x, y, id;
pnt(){x = y = id = 0;}
pnt(int a, int b, int c){x = a, y = b, id = c;}
bool operator ==(const pnt &p){return x == p.x && y == p.y && id == p.id;}
};
pnt a[maxn];
vector<pnt> horz[4][maxn], vert[4][maxn], ru[4][maxn], rd[4][maxn];
bool cmp(const pnt &p, const pnt &q) {
return p.x == q.x ? (q.y == p.y ? p.id < q.id : p.y < q.y) : p.x < q.x;
}
int LB(vector<pnt> &v, pnt P) {
return lower_bound(v.begin(), v.end(), P, cmp) - v.begin();
}
int UB(vector<pnt> &v, pnt P) {
return upper_bound(v.begin(), v.end(), P, cmp) - v.begin();
}
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].id = i;
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();
}
}
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(), cmp);
sort(vert[i][j].begin(), vert[i][j].end(), cmp);
sort(ru[i][j].begin(), ru[i][j].end(), cmp);
sort(rd[i][j].begin(), rd[i][j].end(), cmp);
}
}
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});
pnt cur;
int id, prv = 0, ti, nodes = 0;
auto relax = [&](pnt p, int d, int val) {
int ind = p.id;
if (val >= ti && val < mind[ind][d]) {
mind[ind][d] = val;
pq.push({val, ind * 3 + d});
}
};
auto upd = [&] (vector<pnt> &se, int it, int d, bool type) {
pnt p;
if (type == 0) {
if (it) {
p = se[it-1];
} else {
return;
}
} else {
if (it != se.size()) {
p = se[it];
} else {
return;
}
}
relax(p, d, col(id, p.id));
};
auto to = [&] (vector<pnt> &se, bool type) { //0:prev, 1:next
int it = LB(se, cur);
pnt q;
if (type && it+1 != se.size()) {
q = se[it+1];
} else if (type == 0 && it) {
q = se[it-1];
}
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;
nodes++;
cur = a[id];
vis[id] = 1;
int dir = di[id];
pnt pos = pnt(cur.x + mov[dir][0] * 2 * ti, cur.y + mov[dir][1] * 2 * ti, -1);
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 = pnt(cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti, -1);
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 = pnt(cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti, -1);
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 (stderr)
fever.cpp: In lambda function:
fever.cpp:160:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | if (it != se.size()) {
| ~~~^~~~~~~~~~~~
fever.cpp: In lambda function:
fever.cpp:171:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | if (type && it+1 != se.size()) {
| ~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |