提出 #67385245

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define F(i,n) for(int i=0;i<(n);++i)
struct P{int x,y;};

class S {
    int n,m,K;
    vector<string>* g;
    P *c;
    int *v;    
    double *o; 
    double *d;
    int *idx;
public:
    S(){
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        cin>>n>>m;
        g=new vector<string>(n);
        F(i,n) cin>>g->at(i);

        
        vector<P> tmp;
        F(i,n)F(j,n) if(g->at(i)[j]=='.') tmp.push_back({i,j});
        K=tmp.size();
        c=new P[K];
        v=new int[K];
        o=new double[K];
        d=new double[K];
        idx=new int[K];
        F(i,K){
            c[i]=tmp[i];
            v[i]=0;
            o[i]=0;
            idx[i]=i;
        }


        int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
        unordered_map<long,int> mp;
        mp.reserve(K*2);
        F(i,K) mp[(long)c[i].x<<16 | c[i].y]=i;

        F(i,K){
            int x=c[i].x, y=c[i].y;
            F(d0,4){
                int nx=x+dx[d0], ny=y+dy[d0], cnt=0;
                while(nx>=0&&nx<n&&ny>=0&&ny<n&&g->at(nx)[ny]=='.'){
                    ++cnt;
                    nx+=dx[d0]; ny+=dy[d0];
                }
                o[i]+=cnt;
                long key=(long)nx<<16|ny;
                auto it=mp.find(key);
                if(it!=mp.end()) v[it->second]++;
            }
        }


        double cx=(n-1)/2.0, cy=cx;
        double maxo=0, maxv=0, maxd=0;
        F(i,K){
            double dx0=c[i].x-cx, dy0=c[i].y-cy;
            d[i]=sqrt(dx0*dx0+dy0*dy0);
            maxo=max(maxo,o[i]);
            maxv=max(maxv,(double)v[i]);
            maxd=max(maxd,d[i]);
        }

        sort(idx, idx+K, [&](int a,int b){
            double ma = (v[a]/(maxv+1)) + (o[a]/(maxo+1)) + (d[a]/(maxd+1));
            double mb = (v[b]/(maxv+1)) + (o[b]/(maxo+1)) + (d[b]/(maxd+1));
            return ma < mb;
        });

        
        F(i,K){
            cout<<c[idx[i]].x<<" "<<c[idx[i]].y<<"\n";
        }
    }
};

int main(){
    new S();
    return 0;
}

提出情報

ジャッジ結果