#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point{
ll x, y;
int idx;
Point(){}
Point(ll x, ll y): x(x), y(y){}
Point(ll x, ll y, int idx): x(x), y(y), idx(idx){}
bool operator<(const Point &r)const{
if(x != r.x) return x < r.x;
return y < r.y;
}
};
int n;
Point arr[100002];
int ans;
void makeTrees();
void init();
void solve(int);
int main(){
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%lld %lld", &arr[i].x, &arr[i].y);
arr[i].x*=2, arr[i].y*=2, arr[i].idx = i;
}
makeTrees();
for(int d=0; d<4; d++){
init();
solve(d);
}
printf("%d", ans);
}
const ll INF = 3e18;
vector<Point> order[4];
int idx[4][100002];
int L[4][100002], R[4][100002];
ll tarr[100002];
struct Edge{
int x, dir; ll d;
Edge(){}
Edge(int x, int dir, ll d): x(x), dir(dir), d(d){}
};
void makeTrees(){
for(int i=0; i<n; i++){
for(int j=0; j<4; j++) order[j].push_back(arr[i]);
}
sort(order[0].begin(), order[0].end(), [&](Point &a, Point &b){return a.y != b.y ? a.y < b.y : a.x < b.x;});
sort(order[1].begin(), order[1].end(), [&](Point &a, Point &b){return a.x != b.x ? a.x < b.x : a.y < b.y;});
sort(order[2].begin(), order[2].end(), [&](Point &a, Point &b){return a.y-a.x != b.y-b.x ? a.y-a.x<b.y-b.x : a.x<b.x;});
sort(order[3].begin(), order[3].end(), [&](Point &a, Point &b){return a.y+a.x != b.y+b.x ? a.y+a.x<b.y+b.x : a.x<b.x;});
for(int d=0; d<4; d++) for(int i=0; i<n; i++) idx[d][order[d][i].idx] = i;
/// 0 구분기준: y
for(int i=0; i<n; i++){
int j = i;
while(j+1 < n && order[0][i].y == order[0][j+1].y) j++;
for(int s=i; s<=j; s++) L[0][s] = i, R[0][s] = j;
i=j;
}
/// 1 구분기준: x
for(int i=0; i<n; i++){
int j = i;
while(j+1 < n && order[1][i].x == order[1][j+1].x) j++;
for(int s=i; s<=j; s++) L[1][s] = i, R[1][s] = j;
i=j;
}
/// 2 구분기준: y-x
for(int i=0; i<n; i++){
int j = i;
while(j+1 < n && order[2][i].y-order[2][i].x == order[2][j+1].y-order[2][j+1].x) j++;
for(int s=i; s<=j; s++) L[2][s] = i, R[2][s] = j;
i=j;
}
/// 3 구분기준: y+x
for(int i=0; i<n; i++){
int j = i;
while(j+1 < n && order[3][i].y+order[3][i].x == order[3][j+1].y+order[3][j+1].x) j++;
for(int s=i; s<=j; s++) L[3][s] = i, R[3][s] = j;
i=j;
}
}
bool visited[500002][2];
void init(){
for(int i=0; i<=n; i++) visited[i][0] = visited[i][1] = 0;
}
struct dat{
int x, dir; ll d; int w;
dat(){}
dat(int x, int dir, ll d): x(x), dir(dir), d(d){w=0;}
dat(int x, int dir, ll d, int w): x(x), dir(dir), d(d), w(w){}
bool operator<(const dat &r)const{
return d>r.d;
}
};
priority_queue<dat> pq;
inline ll dist(int x, int y){
return max(abs(arr[x].x-arr[y].x), abs(arr[x].y-arr[y].y));
}
void pickup(int x, int d, ll t){
if(d == 0){ /// 오른쪽 방향
int l, r, i;
/// 1과 만남: tree[2]에서 자기보다 오른쪽
i = idx[2][x];
r = R[2][i], l = lower_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x+t, INF)) - order[2].begin();
if(l<=r && t <= dist(x, order[2][l].idx)) pq.push(dat(2*n + order[2][l].idx, 1, dist(x, order[2][l].idx), 1));
/// 3과 만남: tree[3]에서 자기보다 오른쪽
i = idx[3][x];
r = R[3][i], l = lower_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x+t, INF)) - order[3].begin();
if(l<=r && t <= dist(x, order[3][l].idx)) pq.push(dat(3*n + order[3][l].idx, 3, dist(x, order[3][l].idx), 1));
/// 2와 만남: tree[0]에서 자기보다 오른쪽
i = idx[0][x];
r = R[0][i], l = lower_bound(order[0].begin()+L[0][i], order[0].begin()+R[0][i]+1, Point(arr[x].x+t+t, INF)) - order[0].begin();
if(l<=r && t <= dist(x, order[0][l].idx) / 2) pq.push(dat(order[0][l].idx, 2, dist(x, order[0][l].idx) / 2, 1));
}
else if(d == 1){ /// 아래쪽 방향
int l, r, i;
/// 0과 만남: tree[2]에서 자기보다 왼쪽
i = idx[2][x];
l = L[2][i], r = upper_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x-t, -INF)) - order[2].begin() - 1;
if(l<=r && t <= dist(x, order[2][r].idx)) pq.push(dat(2*n + order[2][r].idx, 0, dist(x, order[2][r].idx), -1));
/// 2과 만남: tree[3]에서 자기보다 오른쪽
i = idx[3][x];
r = R[3][i], l = lower_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x+t, INF)) - order[3].begin();
if(l<=r && t <= dist(x, order[3][l].idx)) pq.push(dat(3*n + order[3][l].idx, 2, dist(x, order[3][l].idx), 1));
/// 3과 만남: tree[1]에서 자기보다 왼쪽
i = idx[1][x];
l = L[1][i], r = upper_bound(order[1].begin()+L[1][i], order[1].begin()+R[1][i]+1, Point(arr[x].x, arr[x].y-t-t)) - order[1].begin() - 1;
if(l<=r && t <= dist(x, order[1][r].idx) / 2) pq.push(dat(n + order[1][r].idx, 3, dist(x, order[1][r].idx) / 2, -1));
}
else if(d == 2){ /// 왼쪽 방향
int l, r, i;
/// 3과 만남: tree[2]에서 자기보다 왼쪽
i = idx[2][x];
l = L[2][i], r = upper_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x-t, -INF)) - order[2].begin() - 1;
if(l<=r && t <= dist(x, order[2][r].idx)) pq.push(dat(2*n + order[2][r].idx, 3, dist(x, order[2][r].idx), -1));
/// 1과 만남: tree[3]에서 자기보다 왼쪽
i = idx[3][x];
l = L[3][i], r = upper_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x-t, INF)) - order[3].begin() - 1;
if(l<=r && t <= dist(x, order[3][r].idx)) pq.push(dat(3*n + order[3][r].idx, 1, dist(x, order[3][r].idx), -1));
/// 0과 만남: tree[0]에서 자기보다 왼쪽
i = idx[0][x];
l = L[0][i], r = upper_bound(order[0].begin()+L[0][i], order[0].begin()+R[0][i]+1, Point(arr[x].x-t-t, arr[x].y)) - order[0].begin() - 1;
if(l<=r && t <= dist(x, order[0][r].idx) / 2) pq.push(dat(order[0][r].idx, 0, dist(x, order[0][r].idx) / 2, -1));
}
else if(d == 3){ /// 위쪽 방향
int l, r, i;
/// 0과 만남: tree[3]에서 자기보다 왼쪽
i = idx[3][x];
l = L[3][i], r = upper_bound(order[3].begin()+L[3][i], order[3].begin()+R[3][i]+1, Point(arr[x].x-t, -INF)) - order[3].begin() - 1;
if(l<=r && t <= dist(x, order[3][r].idx)) pq.push(dat(3*n + order[3][r].idx, 0, dist(x, order[3][r].idx), -1));
/// 2과 만남: tree[2]에서 자기보다 오른쪽
i = idx[2][x];
r = R[2][i], l = lower_bound(order[2].begin()+L[2][i], order[2].begin()+R[2][i]+1, Point(arr[x].x+t, INF)) - order[2].begin();
if(l<=r && t <= dist(x, order[2][l].idx)) pq.push(dat(2*n + order[2][l].idx, 2, dist(x, order[2][l].idx), 1));
/// 1과 만남: tree[1]에서 자기보다 오른쪽
i = idx[1][x];
r = R[1][i], l = lower_bound(order[1].begin()+L[1][i], order[1].begin()+R[1][i]+1, Point(arr[x].x, arr[x].y+t+t)) - order[1].begin();
if(l<=r && t <= dist(x, order[1][l].idx) / 2) pq.push(dat(n + order[1][l].idx, 1, dist(x, order[1][l].idx) / 2, 1));
}
}
void solve(int d){
printf("d: %d\n", d);
int cnt = 0;
for(int i=0; i<n*5; i++) visited[i][0] = visited[i][1] = 0;
pq.push(dat(4*n, d, 0));
while(!pq.empty()){
dat tmp = pq.top(); pq.pop();
if(visited[tmp.x][tmp.w>=0]) continue;
visited[tmp.x][tmp.w>=0] = 1;
int group = tmp.x / n;
int x = tmp.x % n;
// printf("%d %d dir %d - %lld\n", group, x, tmp.dir, tmp.d);
if(group == 4){
if(visited[tmp.x][tmp.w<0]) continue;
cnt++;
pickup(x, tmp.dir, tmp.d);
}
else{
if(!visited[x + n*4][0]){
pq.push(dat(x + n*4, tmp.dir, tmp.d));
}
/// 다음 것도 가능한지 확인
int i = idx[group][x], w = tmp.w;
if(0 <= i + w && i + w < n && L[group][i] == L[group][i+w] && !visited[order[group][i+w].idx][w>=0]){
int X = x, Y = order[group][i+w].idx;
pq.push(dat(group*n + Y, tmp.dir, tmp.d + dist(X, Y) / (group < 2 ? 2 : 1), tmp.w));
}
}
}
ans = max(ans, cnt);
}
Compilation message
fever.cpp: In function 'int main()':
fever.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
fever.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%lld %lld", &arr[i].x, &arr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
