This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int n;
namespace B2 {
const int MAXN = 100'009;
pii tab[MAXN];
int dis[MAXN];
int dir[MAXN];
vector<int> G[MAXN][4];
int f(int a, int b) {
return tab[a].st-tab[b].st+tab[a].nd-tab[b].nd;
}
int dijkstra(int x, int x_dir) {
fill(dis, dis+n, 1e9);
int cnt = 0;
dis[x] = 0;
dir[x] = x_dir;
priority_queue<pii, vector<pii>, greater<pii>> Q;
Q.push({dis[x], x});
while(sz(Q)) {
auto [d_x, x] = Q.top();
Q.pop();
if(d_x!=dis[x]) continue;
cnt++;
for(int y:G[x][dir[x]]) {
int d = f(x, y);
if(d>d_x) continue;
if(d<dis[y]) {
dis[y] = d;
dir[y] = (dir[x]+1)%4;
Q.push({dis[y], y});
}
}
for(int y:G[x][(dir[x]+1)%4]) {
int d = f(x, y);
if(d>d_x) continue;
if(d<dis[y]) {
dis[y] = d;
int ndir = dir[x]-1;
if(ndir<0) ndir+=4;
dir[y] = ndir;
Q.push({dis[y], y});
}
}
}
return cnt;
}
}
namespace B1 {
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
pii tab[10];
int dir[10];
int dis[10];
bool vis[10];
int ans = 0;
int check(int x, int y) {
int d1 = abs(tab[x].st-tab[y].st);
int d2 = abs(tab[x].nd-tab[y].nd);
if(d1!=d2) return -1;
pii p1 = {tab[x].st+dx[dir[x]]*d1, tab[x].nd+dy[dir[x]]*d1};
pii p2 = {tab[y].st+dx[dir[y]]*d1, tab[y].nd+dy[dir[y]]*d1};
if(p1!=p2) return -1;
return d1;
}
void dijkstra() {
// for(int i=0;i<n;i++) cerr << dir[i] << " ";
// cerr << "\n";
vector<int> v(n-1);
iota(all(v), 1);
do {
int cnt = 1;
vector<int> d(n-1, 1e9);
for(int i=0;i<n-1;i++) {
int x = check(v[i], 0);
if(x!=-1) {
d[i] = min(d[i], x);
}
for(int j=i-1;j>=0;j--) {
int y = check(v[i], v[j]);
if(y<d[j]) continue;
d[i] = min(d[i], y);
}
if(d[i]<1e9) cnt++;
else break;
}
ans = max(ans, cnt);
} while(next_permutation(all(v)));
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
if(n<=7) {
for(int i=0;i<n;i++) {
cin >> B1::tab[i].st >> B1::tab[i].nd;
}
for(int i=0;i<(1<<(2*n));i++) {
for(int j=0;j<2*n;j+=2) {
bool a = i&(1<<j);
bool b = i&(1<<(j+1));
B1::dir[j/2] = 2*a+b;
}
B1::dijkstra();
}
cout << B1::ans << "\n";
return 0;
}
using namespace B2;
for(int i=0;i<n;i++) {
int a, b;
cin >> a >> b;
tab[i] = {a-b, a+b};
// cerr << i << ": " << tab[i] << "\n";
}
for(int i=0;i<n;i++) {
auto [a1, b1] = tab[i];
for(int j=0;j<n;j++) {
auto [a2, b2] = tab[j];
if(a1>a2&&b1==b2) {
G[i][0].pb(j);
}
if(a1==a2&&b2>b1) {
G[i][1].pb(j);
}
if(a1<a2&&b1==b2) {
G[i][2].pb(j);
}
if(a1==a2&&b2<b1) {
G[i][3].pb(j);
}
}
}
int ans = 0;
for(int i=0;i<4;i++) {
ans = max(ans, dijkstra(0, i));
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |