/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
int N;
int X[N_MAX + 2], Y[N_MAX + 2];
int order[N_MAX + 2];
unordered_map <int, deque <int>> D1, D2;
int min_len[N_MAX + 2][4];
priority_queue <tuple <int, int, int>> q;
/*
1\ 0 /0
\|/
1-x-3
/|\
2/ 2 \3
*/
void go (int i, int di) {
if (di == 0 || di == 3) {
int dj = (di == 0 ? 1 : 2);
int d = X[i] - Y[i];
while (D1[d].empty() == false) {
int j = D1[d].back();
if (min_len[j][dj] != -1) {
D1[d].pop_back();
} else if (X[i] + min_len[i][di] <= X[j]) {
D1[d].pop_back();
min_len[j][dj] = X[j] - X[i];
q.push(make_tuple(-min_len[j][dj], j, dj));
} else {
break;
}
}
}
if (di == 1 || di == 0) {
int dj = (di == 1 ? 2 : 3);
int d = X[i] + Y[i];
while (D2[d].empty() == false) {
int j = D2[d].front();
if (min_len[j][dj] != -1) {
D2[d].pop_front();
} else if (X[i] - min_len[i][di] >= X[j]) {
D2[d].pop_front();
min_len[j][dj] = X[i] - X[j];
q.push(make_tuple(-min_len[j][dj], j, dj));
} else {
break;
}
}
}
if (di == 2 || di == 1) {
int dj = (di == 2 ? 3 : 0);
int d = X[i] - Y[i];
while (D1[d].empty() == false) {
int j = D1[d].front();
if (min_len[j][dj] != -1) {
D1[d].pop_front();
} else if (X[i] - min_len[i][di] >= X[j]) {
D1[d].pop_front();
min_len[j][dj] = X[i] - X[j];
q.push(make_tuple(-min_len[j][dj], j, dj));
} else {
break;
}
}
}
if (di == 3 || di == 2) {
int dj = (di == 3 ? 0 : 1);
int d = X[i] + Y[i];
while (D2[d].empty() == false) {
int j = D2[d].back();
if (min_len[j][dj] != -1) {
D2[d].pop_back();
} else if (X[i] + min_len[i][di] <= X[j]) {
D2[d].pop_back();
min_len[j][dj] = X[j] - X[i];
q.push(make_tuple(-min_len[j][dj], j, dj));
} else {
break;
}
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("input.txt", "r", stdin);
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 : {0, 1, 2, 3}) {
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);
}
for (int i = 1; i <= N; i++) {
for (int di : {0, 1, 2, 3}) {
min_len[i][di] = -1;
}
}
min_len[1][d1] = 0; go(1, d1);
while (q.empty() == false) {
int trash, i, di;
tie(trash, i, di) = q.top();
q.pop();
go(i, di);
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int di : {0, 1, 2, 3}) {
if (min_len[i][di] != -1) {
cnt++;
break;
}
}
}
answer = max(answer, cnt);
D1.clear(); D2.clear();
}
cout << answer << "\n";
return 0;
}
Compilation message
fever.cpp: In function 'int main()':
fever.cpp:104:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
