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;
vector<array<int,3>> v;
const int mxN = (int)3e3+10;
const int X[] = {1,0,-1,0,0};
const int Y[] = {0,1,0,-1,0};
int n, d[mxN], x[mxN], y[mxN], b[mxN];
int D(int i, int di, int j, int dj){
return abs((x[i]+X[di])-(x[j]+X[dj]))+abs((y[i]+Y[di])-(y[j]+Y[dj]));
}
int ti(int i, int j){
int dis = D(i,4,j,4)/2;
if((x[i]+X[d[i]]*dis)!=(x[j]+X[d[j]]*dis)) return -1;
if((y[i]+Y[d[i]]*dis)!=(y[j]+Y[d[j]]*dis)) return -1;
return D(i,4,j,4);
}
int main(){
cin >> n; b[0]=1; int ans = 1;
for(int i = 0; i < n; i++)
cin >> x[i] >> y[i];
for(int i = n-1; i >= 0; i--)
x[i]-=x[0], y[i]-=y[0],x[i]<<=1,y[i]<<=1;
for(int t = 0; t < 4; t++){
fill(b+1,b+n,0); v.clear();
for(int i = 0; i < n; i++){
if(abs(y[i])<x[i]) d[i] = 2;
else if(abs(y[i])<=-x[i]) d[i] = 0;
else if(abs(x[i])<=y[i]) d[i] = 3;
else if(abs(x[i])<=-y[i]) d[i] = 1;
}
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(ti(i,j)!=-1) v.push_back({ti(i,j),i,j});
sort(begin(v),end(v));
for(auto [t,i,j] : v) b[i]=b[j]=(b[i]|b[j]);
ans = max(ans, accumulate(b,b+n,0));
for(int i = 1; i < n; i++)swap(x[i],y[i]),x[i]*=-1;
}
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... |