#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mx = 1e5 + 5;
void solve() {
int n; cin >> n;
vector<pair<int, int>> p(n);
vector<int> dir(n);
for (auto& x : p) { cin >> x.first >> x.second; x.first *= 2; x.second *= 2; }
int x1 = p[0].first, x2 = p[0].second;
for (auto& x : p) x.first -= x1, x.second -= x2;
int ans = 0;
for (int i = 0; i < 4; i++) {
cout << "roation: " << i << endl;
dir[0] = 0; //u
for (int j = 1; j < n; j++) {
auto [x, y] = p[j];
if (y < -abs(x)) { //d
dir[j] = 0;
} else if (y > abs(x)) { //u
dir[j] = 1;
} else if (x > abs(y)) { //l
dir[j] = 2;
} else if (x < -abs(y)) { //r
dir[j] = 3;
} else if (y < 0) { //u
dir[j] = 0;
} else if (x == 0) { // d
dir[j] = 1;
} else if (x > 0) { // l
dir[j] = 2;
} else if (x < 0) { //r
dir[j] = 3;
}
}
map<int, set<pair<int, int>>> a[4], b[4], c[4], d[4]; //x - y: {x, id}, x + y: {x, id}, x : {y, id}, y : {x, id}
auto ad = [&](int dir, int x, int y, int id) {
a[dir][x - y].insert({ x,id });
b[dir][x + y].insert({ x,id });
if (dir == 0 || dir == 1) c[dir][x].insert({ y, id });
if (dir == 2 || dir == 3) d[dir][y].insert({ x, id });
};
auto rem = [&](int dir, int x, int y, int id) {
a[dir][x - y].erase({ x,id });
b[dir][x + y].erase({ x,id });
if (dir == 0 || dir == 1) c[dir][x].erase({ y, id });
if (dir == 2 || dir == 3) d[dir][y].erase({ x, id });
};
for (int j = 0; j < n; j++) {
ad(dir[j], p[j].first, p[j].second, j);
}
vector<int> vis(n, 0);
set<pair<int, pair<int, int>>> s; // {time, {id, prev}}
auto add = [&](int id, int t) {
if (id == -1) return;
auto [x, y] = p[id];
if (dir[id] == 0) { //u
auto e = a[2][x - y].lower_bound({ x + t, 0 });
if (e != a[2][x - y].end()) s.insert({ e->first - x, {e->second, id} });
auto f = b[3][x + y].upper_bound({ x - t, mx });
f = (f == b[3][x + y].begin()) ? b[3][x + y].end() : prev(f);
if (f != b[3][x + y].end()) s.insert({ x - f->first , {f->second, id} });
auto g = c[1][x].lower_bound({ y + t * 2, 0 });
if (g != c[1][x].end()) s.insert({ (g->first - y) / 2, {g->second, id} });
} else if (dir[id] == 1) { //d
auto e = a[2][x + y].lower_bound({ x + t, 0 });
if (e != a[2][x + y].end()) s.insert({ e->first - x, {e->second, id} });
auto f = b[3][x - y].upper_bound({ x - t, mx });
f = (f == b[3][x - y].begin()) ? b[3][x - y].end() : prev(f);
if (f != b[3][x - y].end()) s.insert({ x - f->first , {f->second, id} });
auto g = c[0][x].upper_bound({ y - t * 2, mx });
g = (g == c[0][x].begin()) ? c[0][x].end() : prev(g);
if (g != c[0][x].end()) s.insert({ (y - g->first) / 2, {g->second, id} });
} else if (dir[id] == 2) { //l
auto e = a[0][x - y].upper_bound({ x - t, 0 });
e = (e == a[0][x - y].begin()) ? a[0][x - y].end() : prev(e);
if (e != a[0][x - y].end()) s.insert({ x - e->first, {e->second, id} });
auto f = b[1][x + y].upper_bound({ x - t, mx });
f = (f == b[1][x + y].begin()) ? b[1][x + y].end() : prev(f);
if (f != b[1][x + y].end()) s.insert({ x - f->first , {f->second, id} });
auto g = d[3][y].upper_bound({ x + t * 2, 0 });
g = (g == d[3][y].begin()) ? d[3][y].end() : prev(g);
if (g != d[3][y].end()) s.insert({ (x - g->first) / 2, {g->second, id} });
} else { //r
auto e = a[0][x + y].lower_bound({ x - t, 0 });
if (e != a[0][x + y].end()) s.insert({ e->first - x, {e->second, id} });
auto f = b[1][x - y].lower_bound({ x - t, mx });
if (f != b[1][x - y].end()) s.insert({ f->first - x, {f->second, id} });
auto g = d[2][y].lower_bound({ x + t * 2, 0 });
if (g != d[2][y].end()) s.insert({ (g->first - x) / 2, {g->second, id} });
}
};
s.insert({ 0, { 0, -1 } });
int res = 0;
while (s.size()) {
auto [a, b] = *s.begin();
auto [c, d] = b;
a++;
s.erase(s.begin());
if (vis[c]) continue;
rem(dir[c], p[c].first, p[c].second, c);
vis[c] = 1; res++;
add(c, a); add(d, a);
}
ans = max(ans, res);
//rotate
for (auto& x : p) x = { -x.second, x.first };
}
cout << ans << endl;
}
int32_t main() {
int t = 1;
//cin >> t;
while (t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
