これは何とか思いつけた。
https://yukicoder.me/problems/no/1121
問題
N個の格子点の座標が与えられる。
このうちN/90個を選択し、互いの距離が10以上となるようにせよ。
解法
格子点全体を何らかの条件で90個のグループに分類することを考える。
その際、同グループ内の頂点同士の距離が10以上になるようにしよう。
例えば横10個*縦9個の矩形範囲を繰り返して平面を敷き詰めたとする。
矩形内の相対位置が同じ等しい格子点同士について、横の隣の矩形内の点との距離は10保てる。
ただこれだと上下の矩形内との点との距離は9となり条件を見たさない。
そこで、矩形を敷き詰める際に1行ごとに横に5ずつずらしていこう。
そして最も数が多いグループの頂点群を答えればよい。
int N; int X[303030],Y[303030]; vector<int> S[10][9]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>X[i]>>Y[i]; y=Y[i]%9; x=(X[i]+Y[i]/9*5)%10; S[x][y].push_back(i); } FOR(x,10) FOR(y,9) if(S[x][y].size()*90>=N) { cout<<S[x][y].size()<<endl; FORR(s,S[x][y]) cout<<s+1<<" "; cout<<endl; return; } assert(0); }
まとめ
途中もっと複雑な形状も考えたけど、最終的にはシンプルなものに落ち着いた。