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>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int INF = 1e18;
int X[100005];
int Y[100005];
int dis[100005][4];
bool vis[100005];
vector<vector<int>> adj;
int simulate(int dir2, int N) {
//cout << "Direction : "<< dir2 << '\n';
int i, j;
for(i=0;i<N;i++) {
for(j=0;j<4;j++) dis[i][j] = INF;
}
for(i=0;i<N;i++) vis[i] = false;
dis[0][dir2] = 0;
priority_queue<P,vector<P>,greater<P>> PQ;
PQ.push(P(0,dir2));
while(!PQ.empty()) {
P k = PQ.top();
PQ.pop();
if(vis[k.second/4]) continue;
vis[k.second/4] = true;
int id = k.second / 4;
int dir = k.second % 4;
//cout << id << ' ' << dir << '\n';
for(int i=0;i<N;i++) {
if(i==id) continue;
if(abs(X[i]-X[id])!=abs(Y[i]-Y[id])) continue;
int d = abs(X[i] - X[id]);
int val = 2* (X[i] < X[id]) + (Y[i] < Y[id]);
if(val==3) {
if(dir>=2) {
if(dis[i][3-dir]>d && dis[id][dir]<=d) {
dis[i][3-dir] = d;
PQ.push(P(dis[i][3-dir],4*i+3-dir));
}
}
}
if(val==2) {
if(dir==1||dir==2) {
if(dis[i][(5-dir)%4]>d&&dis[id][dir]<=d) {
dis[i][(5-dir)%4] = d;
PQ.push(P(dis[i][(5-dir)%4],4*i+(5-dir)%4));
}
}
}
if(val==1) {
if(dir==0||dir==3) {
if(dis[i][(5-dir)%4]>d&&dis[id][dir]<=d) {
dis[i][(5-dir)%4] = d;
PQ.push(P(dis[i][(5-dir)%4],4*i+(5-dir)%4));
}
}
}
if(val==0) {
if(dir<=1) {
if(dis[i][3-dir]>d&&dis[id][dir]<=d) {
dis[i][3-dir] = d;
PQ.push(P(dis[i][3-dir],4*i+3-dir));
}
}
}
}
for(i=0;i<N;i++) {
if(i==id) continue;
if(dir==0) {
if(X[id]<X[i]&&Y[i]==Y[id]) {
int d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2;
if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) {
dis[i][(dir+2)%4] = d;
PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
}
}
}
if(dir==2) {
if(X[id]>X[i]&&Y[i]==Y[id]) {
int d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2;
if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) {
dis[i][(dir+2)%4] = d;
PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
}
}
}
if(dir==1) {
if(X[id]==X[i]&&Y[id]<Y[i]) {
int d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2;
if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) {
dis[i][(dir+2)%4] = d;
PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
}
}
}
if(dir==3) {
if(X[id]==X[i]&&Y[id]>Y[i]) {
int d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2;
if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) {
dis[i][(dir+2)%4] = d;
PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
}
}
}
}
}
int ans = 0;
for(i=0;i<N;i++) {
int mi = INF;
for(j=0;j<4;j++) mi = min(mi, dis[i][j]);
if(mi != INF) ans++;
}
return ans;
}
map<int,vector<int>> M1, M2;
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
int i, j;
for(i=0;i<N;i++) cin >> X[i] >> Y[i];
for(i=0;i<N;i++) {
X[i] *= 2;
Y[i] *= 2;
}
adj.resize(N);
int ma = 0;
for(i=0;i<4;i++) ma = max(ma, simulate(i, N));
cout <<ma;
}
Compilation message (stderr)
fever.cpp: In function 'int main()':
fever.cpp:122:12: warning: unused variable 'j' [-Wunused-variable]
122 | int i, j;
| ^
# | 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... |