Submission #1330577

#TimeUsernameProblemLanguageResultExecution timeMemory
1330577Ahmed57IOI Fever (JOI21_fever)C++20
25 / 100
5089 ms5712 KiB
#include "bits/stdc++.h"

using namespace std;
#define int long long 
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    vector<pair<int,int>> v(n+1);
    for(int i = 1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
        v[i].first*=2;
        v[i].second*=2;
    }
    int ma = 0;
    for(int dir = 0;dir<4;dir++){
        int lol[n+1];
        lol[1] = dir;
        for(int i = 2;i<=n;i++){
            if(v[i].first>v[1].first&&v[i].second>v[1].second){
                if(abs(v[i].first-v[1].first)<abs(v[i].second-v[1].second)){
                    lol[i] = 1;
                }else if(abs(v[i].first-v[1].first)>abs(v[i].second-v[1].second)){
                    lol[i] = 3;
                }else{
                    if(dir==0){
                        lol[i] = 3;
                    }else if(dir==1){
                        lol[i] = 1;
                    }else if(dir==2){
                        lol[i] = 1;
                    }else lol[i] = 3;
                }
            }
            if(v[i].first<v[1].first&&v[i].second>v[1].second){
                if(abs(v[i].first-v[1].first)<abs(v[i].second-v[1].second)){
                    lol[i] = 1;
                }else if(abs(v[i].first-v[1].first)>abs(v[i].second-v[1].second)){
                    lol[i] = 2;
                }else{
                    if(dir==0){
                        lol[i] = 2;
                    }else if(dir==1){
                        lol[i] = 1;
                    }else if(dir==3){
                        lol[i] = 1;
                    }else lol[i] = 2;
                }
            }
            if(v[i].first>v[1].first&&v[i].second<v[1].second){
                if(abs(v[i].first-v[1].first)<abs(v[i].second-v[1].second)){
                    lol[i] = 0;
                }else if(abs(v[i].first-v[1].first)>abs(v[i].second-v[1].second)){
                    lol[i] = 3;
                }else{
                    if(dir==1){
                        lol[i] = 3;
                    }else if(dir==0){
                        lol[i] = 0;
                    }else if(dir==2){
                        lol[i] = 0;
                    }else lol[i] = 3;
                }
            }
            if(v[i].first<v[1].first&&v[i].second<v[1].second){
                if(abs(v[i].first-v[1].first)<abs(v[i].second-v[1].second)){
                    lol[i] = 0;
                }else if(abs(v[i].first-v[1].first)>abs(v[i].second-v[1].second)){
                    lol[i] = 2;
                }else{
                    if(dir==1){
                        lol[i] = 2;
                    }else if(dir==0){
                        lol[i] = 0;
                    }else if(dir==3){
                        lol[i] = 0;
                    }else lol[i] = 2;
                }
            }
            if(v[i].first==v[1].first&&v[i].second>v[1].second){
                if(dir==0||dir==1){
                    lol[i] = 1;
                }else{
                    lol[i] = dir;
                }
            }if(v[i].first==v[1].first&&v[i].second<v[1].second){
                if(dir==0||dir==1){
                    lol[i] = 0;
                }else{
                    lol[i] = dir;
                }
            }if(v[i].first>v[1].first&&v[i].second==v[1].second){
                if(dir==2||dir==3){
                    lol[i] = 3;
                }else{
                    lol[i] = dir;
                }
            }if(v[i].first<v[1].first&&v[i].second==v[1].second){
                if(dir==2||dir==3){
                    lol[i] = 2;
                }else{
                    lol[i] = dir;
                }
            }
        }
        priority_queue<pair<int,int>> q;
        int vis[n+1] = {0};
        memset(vis,-1,sizeof vis);
        q.push({-0,1});
        vis[1] = 0;
        while(!q.empty()){
            int ti = -q.top().first;
            int x = q.top().second;
            q.pop();
            if(vis[x]<ti)continue;
            for(int j = 1;j<=n;j++){
                int dif = v[j].first-v[x].first;
                if(dif!=0){
                    int lo = dx[lol[x]]-dx[lol[j]];
                    if(lo==0)continue;
                    int nti = dif/lo;
                    if(nti>=ti&&v[x].second+nti*dy[lol[x]]==v[j].second+nti*dy[lol[j]]){
                        if(vis[j]==-1||vis[j]>nti){
                            vis[j] = nti;
                            q.push({-nti,j});
                        }
                    }
                }else{
                    dif = v[j].second-v[x].second;
                    int lo = dy[lol[x]]-dy[lol[j]];
                    if(lo==0)continue;
                    int nti = dif/lo;
                    if(nti>=ti&&v[x].first+nti*dx[lol[x]]==v[j].first+nti*dx[lol[j]]){
                        if(vis[j]==-1||vis[j]>nti){
                            vis[j] = nti;
                            q.push({-nti,j});
                        }
                    }
                }
            }
        }
        int cnt = 0;
        for(int i = 1;i<=n;i++){
            cnt+=(vis[i]!=-1);
        }
        ma = max(ma,cnt);
    }
    cout<<ma<<endl;
    return 0;
}
//
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...