제출 #1330574

#제출 시각아이디문제언어결과실행 시간메모리
1330574Ahmed57IOI Fever (JOI21_fever)C++20
19 / 100
1 ms344 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;
    }
    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;
                }
            }
        }
        priority_queue<pair<int,int>> q;
        int vis[n+1] = {0};
        q.push({-0,1});
        vis[1] = 1;
        while(!q.empty()){
            int ti = -q.top().first;
            int x = q.top().second;
            q.pop();
            for(int j = 1;j<=n;j++){
                if(vis[j])continue;
                int dif = v[j].first-v[x].first;
                if(lol[j]<2&&lol[x]<2)continue;
                if(lol[j]>1&&lol[x]>1)continue;
                if(lol[x]>1){
                    int nti = dif/dx[lol[x]];
                    if(nti>=ti&&v[x].second+nti*dy[lol[x]]==v[j].second+nti*dy[lol[j]]){
                        vis[j] = 1;
                        q.push({-nti,j});
                    }
                }else{
                    int nti = dif/(-dx[lol[j]]);
                    if(nti>=ti&&v[x].second+nti*dy[lol[x]]==v[j].second+nti*dy[lol[j]]){
                        vis[j] = 1;
                        q.push({-nti,j});
                    }
                }
            }
        }
        int cnt = 0;
        for(int i = 1;i<=n;i++){
            cnt+=vis[i];
        }
        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...