/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
int N;
int X[N_MAX + 2], Y[N_MAX + 2];
int order[N_MAX + 2];
unordered_map <int, deque <int>> D1, D2;
int dir[N_MAX + 2];
int min_len[N_MAX + 2];
priority_queue <pair <int, int>> q;
/*
1\ 0 /0
\|/
1-x-3
/|\
2/ 2 \3
*/
void go (int i) {
if (dir[i] == UP || dir[i] == RIGHT) {
int d = X[i] - Y[i];
while (D1[d].empty() == false) {
int j = D1[d].back();
if (min_len[j] != -1) {
D1[d].pop_back();
} else if (X[i] + min_len[i] <= X[j]) {
D1[d].pop_back();
min_len[j] = X[j] - X[i];
q.push({-min_len[j], j});
} else {
break;
}
}
}
if (dir[i] == LEFT || dir[i] == UP) {
int d = X[i] + Y[i];
while (D2[d].empty() == false) {
int j = D2[d].front();
if (min_len[j] != -1) {
D2[d].pop_front();
} else if (X[i] - min_len[i] >= X[j]) {
D2[d].pop_front();
min_len[j] = X[i] - X[j];
q.push({-min_len[j], j});
} else {
break;
}
}
}
if (dir[i] == DOWN || dir[i] == LEFT) {
int d = X[i] - Y[i];
while (D1[d].empty() == false) {
int j = D1[d].front();
if (min_len[j] != -1) {
D1[d].pop_front();
} else if (X[i] - min_len[i] >= X[j]) {
D1[d].pop_front();
min_len[j] = X[i] - X[j];
q.push({-min_len[j], j});
} else {
break;
}
}
}
if (dir[i] == RIGHT || dir[i] == DOWN) {
int d = X[i] + Y[i];
while (D2[d].empty() == false) {
int j = D2[d].back();
if (min_len[j] != -1) {
D2[d].pop_back();
} else if (X[i] + min_len[i] <= X[j]) {
D2[d].pop_back();
min_len[j] = X[j] - X[i];
q.push({-min_len[j], j});
} else {
break;
}
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> X[i] >> Y[i];
}
iota(order + 1, order + N + 1, 1);
sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
return X[i] < X[j];
});
int answer = 0;
for (int d1 : {UP, LEFT, DOWN, RIGHT}) {
for (int k = 1; k <= N; k++) {
int i = order[k];
D1[X[i] - Y[i]].push_back(i);
D2[X[i] + Y[i]].push_back(i);
}
dir[1] = d1;
for (int i = 1; i <= N; i++) {
if (abs(X[i] - X[1]) > abs(Y[i] - Y[1])) {
dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
} else if (abs(Y[i] - Y[1]) > abs(X[i] - X[1])) {
dir[i] = (Y[i] < Y[1] ? UP : DOWN);
} else {
if (d1 == UP) {
if (Y[i] < Y[1]) {
dir[i] = UP;
} else {
dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
}
}
if (d1 == LEFT) {
if (X[i] > X[1]) {
dir[i] = LEFT;
} else {
dir[i] = (Y[i] < Y[1] ? UP : DOWN);
}
}
if (d1 == DOWN) {
if (Y[i] > Y[1]) {
dir[i] = DOWN;
} else {
dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
}
}
if (d1 == RIGHT) {
if (X[i] > X[1]) {
dir[i] = RIGHT;
} else {
dir[i] = (Y[i] < Y[1] ? UP : DOWN);
}
}
}
}
fill(min_len + 1, min_len + N + 1, -1);
min_len[1] = 0; go(1);
while (q.empty() == false) {
int i = q.top().second;
q.pop();
go(i);
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
cnt += (min_len[i] != -1);
}
answer = max(answer, cnt);
D1.clear(); D2.clear();
}
cout << answer << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
