#include <bits/stdc++.h>
using namespace std;
struct house {
int x, y;
};
const int MAX_N = 2e5;
const int INF = 5e8;
int dir[MAX_N], t[MAX_N];
house houses[MAX_N];
unordered_map<int, set<pair<int, int>>> diag1, diag2, vert, horiz;
vector<int> q;
void visitt( set<pair<int, int>> &s, int l, int r, int i, int d ) {
vector<int> del;
auto p = s.lower_bound( { l, 0 } );
while ( p != s.end() && p->first <= r ) {
int j = p->second;
if ( dir[j] == d ) {
del.push_back( j );
q.push_back( j );
if ( houses[i].x == houses[j].x )
t[j] = abs( houses[j].y - houses[i].y ) / 2;
else if ( houses[i].y == houses[j].y )
t[j] = abs( houses[j].x - houses[j].x ) / 2;
else
t[j] = abs( houses[j].x - houses[i].x );
}
p++;
}
for ( int j: del ) {
diag1[houses[j].x + houses[j].y].erase( { houses[j].x, j } );
diag2[houses[j].x - houses[j].y].erase( { houses[j].x, j } );
vert[houses[j].x].erase( { houses[j].y, j } );
horiz[houses[j].y].erase( { houses[j].x, j } );
}
}
int main() {
int n;
cin >> n;
for ( int i = 0; i < n; i++ ) {
cin >> houses[i].x >> houses[i].y;
if ( i != 0 ) {
houses[i].x -= houses[0].x;
houses[i].y -= houses[0].y;
}
}
for ( int i = 1; i < n; i++ ) {
if ( houses[i].x > 0 ) {
if ( houses[i].y > 0 )
dir[i] = (houses[i].x > houses[i].y ? 3 : 1);
else
dir[i] = (houses[i].x > houses[i].y ? 3 : 2);
} else {
if ( houses[i].y > 0 )
dir[i] = (houses[i].x > houses[i].y ? 3 : 2);
else
dir[i] = (houses[i].x > houses[i].y ? 3 : 2);
}
}
int maxVisited = 0;
for ( int d = 0; d < 4; d++ ) {
diag1.clear();
diag2.clear();
for ( int i = 1; i < n; i++ ) {
diag1[houses[i].x + houses[i].y].insert( { houses[i].x, i } );
diag2[houses[i].x - houses[i].y].insert( { houses[i].x, i } );
vert[houses[i].x].insert( { houses[i].y, i } );
horiz[houses[i].y].insert( { houses[i].x, i } );
}
int visited = 0;
q.clear();
q.push_back( 0 );
dir[0] = d;
t[0] = 0;
while ( visited < q.size() ) {
int pos = visited + rand() % (q.size() - visited);
int i = q[visited];
visited++;
//printf( "%d (%d %d) %d %d\n", i, houses[i].x, houses[i].y, t[i], dir[i] );\
int x = houses[i].x, y = houses[i].y;
if ( dir[i] == 0 ) {
visitt( vert[x], y + t[i], INF, i, 1 );
visitt( diag1[x + y], -INF, x - t[i], i, 2 );
visitt( diag2[x - y], x + t[i], INF, i, 3 );
} else if ( dir[i] == 1 ) {
visitt( vert[x], -INF, y - t[i], i, 0 );
visitt( diag1[x + y], x + t[i], INF, i, 3 );
visitt( diag2[x - y], -INF, x - t[i], i, 2 );
} else if ( dir[i] == 2 ) {
visitt( horiz[y], x + t[i], INF, i, 3 );
visitt( diag1[x + y], x + t[i], INF, i, 0 );
visitt( diag2[x - y], x + t[i], INF, i, 1 );
} else if ( dir[i] == 3 ) {
visitt( horiz[y], -INF, x - t[i], i, 2 );
visitt( diag1[x + y], -INF, x - t[i], i, 1 );
visitt( diag2[x - y], -INF, x - t[i], i, 0 );
}
}
//printf( "DIR %d: %d\n", d, visited );
maxVisited = max( maxVisited, visited );
}
cout << maxVisited;
return 0;
}
/*
* d == 0 sus
* d == 1 jos
* d == 2 dreapta
* d == 3 stanga
*/
Compilation message
fever.cpp:93:13: warning: multi-line comment [-Wcomment]
93 | //printf( "%d (%d %d) %d %d\n", i, houses[i].x, houses[i].y, t[i], dir[i] );\
| ^
fever.cpp: In function 'int main()':
fever.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | while ( visited < q.size() ) {
| ~~~~~~~~^~~~~~~~~~
fever.cpp:89:17: warning: unused variable 'pos' [-Wunused-variable]
89 | int pos = visited + rand() % (q.size() - visited);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
