题解归档 - cf2225E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2225E
• 本地来源：problems/cf2225E/idea.md
• 题目链接：https://codeforces.com/contest/2225/problem/E
• 原始标题：cf2225E - Covering Points with Circles

思路

cf2225E - Covering Points with Circles

Pattern

Use a hexagonal packing of equal-radius circles. Adjacent centers are 2r
apart horizontally and sqrt(3)r apart vertically, with alternate rows shifted
by r.

Claim

The infinite hexagonal packing has covered area density:

pi r^2 / (2 sqrt(3) r^2) = pi / (2 sqrt(3)) ~= 90.69%.

For the random test model, a translated packing should cover more than the
required 89% of the uniformly generated points with high probability. The
implementation samples a deterministic grid of translations and keeps the one
that covers the most input points; it also tries fixed-seed extra translations
if needed.

Construction

For a shift (sx,sy), assign each point to the nearby centers in at most three
neighboring rows and columns. If a point is inside one of those circles, record
that center. The selected centers are a subset of one hexagonal lattice, so any
two selected circles have distance at least 2r and do not overlap with
positive area.

The best sampled shift is printed. The number of printed centers is at most the
number of covered points and therefore at most n.

Checks

• python tools/run_exe.py cf2225E produced a valid sample output.
• Inline sample checker: k=1, covered 4/4.
• python tools/stress2.py cf2225E -n 100 --keep-fail passed with the
  geometry-circles checker.

Risk

This is a probabilistic construction matched to the statement's random test
model, not an adversarial guarantee for arbitrary point sets.

代码

来源：problems/cf2225E/solution.cpp

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

ll floordiv(ll a,ll b){
    if(a>=0) return a/b;
    return -((-a+b-1)/b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll r;
    cin>>n>>r;
    vector<pair<ll,ll>> p(n);
    for(auto &i:p) cin>>i.first>>i.second;
    auto coveredBy=[&](ll cx,ll cy,pair<ll,ll> q){
        ll dx=q.first-cx,dy=q.second-cy;
        return dx*dx+dy*dy<=r*r;
    };
    long double sx0=0,sy0=0;
    for(auto [x,y]:p){
        sx0+=x;
        sy0+=y;
    }
    ll cx0=llround(sx0/n),cy0=llround(sy0/n);
    int one=0;
    for(auto q:p) if(coveredBy(cx0,cy0,q)) one++;
    if(one*100>=89*n){
        cout<<1<<"\n"<<cx0<<" "<<cy0<<"\n";
        return 0;
    }
    ll h=1;
    while(h*h<3*r*r) h++;
    vector<pair<ll,ll>> bestCenters;
    int best=-1;
    auto eval=[&](ll sx,ll sy){
        vector<pair<ll,ll>> cur;
        cur.reserve(n);
        int got=0;
        for(auto [px,py]:p){
            bool ok=false;
            pair<ll,ll> take={0,0};
            ll row=floordiv(py-sy,h);
            for(ll dj=-1;dj<=1&&!ok;dj++){
                ll j=row+dj;
                ll cy=sy+j*h;
                ll off=sx+((j&1)?r:0);
                ll col=floordiv(px-off,2*r);
                for(ll di=-1;di<=1;di++){
                    ll cx=off+(col+di)*2*r;
                    if(coveredBy(cx,cy,{px,py})){
                        ok=true;
                        take={cx,cy};
                        break;
                    }
                }
            }
            if(ok){
                got++;
                cur.push_back(take);
            }
        }
        if(got>best){
            sort(cur.begin(),cur.end());
            cur.erase(unique(cur.begin(),cur.end()),cur.end());
            best=got;
            bestCenters=cur;
        }
    };
    const int S=25;
    for(int i=0;i<S;i++){
        for(int j=0;j<S;j++){
            eval((2*r*i)/S,(h*j)/S);
            if(best*100>=89*n) break;
        }
        if(best*100>=89*n) break;
    }
    mt19937 rng(2225);
    for(int it=0;it<300&&best*100<89*n;it++){
        ll sx=rng()%(2*r);
        ll sy=rng()%h;
        eval(sx,sy);
    }
    if(bestCenters.empty()) bestCenters.push_back({cx0,cy0});
    cout<<bestCenters.size()<<"\n";
    for(auto [x,y]:bestCenters) cout<<x<<" "<<y<<"\n";
    return 0;
}