题解：CF2225E Covering Points with Circles

· · 题解

我能够在没有学过平面几何的情况下切掉 E 吗？这可能吗？这能被做到吗？

思路分析

观察发现，题目要求只需使 89\% 的点在圆的内部，还保证点是随机生成的，点的数量又相对较大，还关了 hack，这启示我们只需将大部分位置覆盖掉就可以了。

又注意到圆的数量不限，且至多为点的数量，考虑按照类似蜂巢那样来排列圆，就是将圆像堆起来一样紧密排列。

由于圆心必须是整点，你让圆心向上取整就行，对答案影响不大。

对于每一个点，判断其所在圆的位置并储存即可，不用真的把所有圆都弄出来。这样可以保证圆的数量小于等于 n。

正确性证明

考虑到数据随机，点数又较大，只需要让圆覆盖大约 89\% 的面积即可。发现这样排列圆可能是圆最紧密的排序方式，所以如此构造即可。

其面积占比可以用初中几何证明。考虑紧挨着的三个圆，它们三个圆心所构成的正三角形（如上图的 \triangle\text{ABC}）通过无限拼接可以构成整个图形，因此圆在这个正三角形的占比就是圆在整个平面的占比。

不妨设正三角形的边长为 2，则其高为 \sqrt 3，总面积为 \sqrt3，而圆所占的面积为三个圆心角为 60^\circ 的扇形，相当于一个半圆，其面积为 \frac{\pi}{2}，则圆的占比为 \frac{\pi}{2}\div\sqrt3\approx0.906899，也就是 90.69\% 左右。考虑到点全部都是整点，尽管部分圆心有一定的偏差，但仍然可以覆盖 89\% 的面积。

代码具体实现

考虑按照上图的方式摆放，则各列之间圆心的距离均为 \sqrt3r，每行间相邻的圆的距离为 2r。

对于每一个点，找到其左下的离它最近的圆心，并依次判断这个点是否在其左下、左上、右下、右边、右上的圆的内部即可。（upd：其实右上和右下可能不用判的）

至于寻找，可以通过直接计算或二分的方式来寻找。我是不会告诉你我调了十万年也没有调出来的，所以我选择了另一种类似于倍增的方式。具体见代码。

注意特判样例。

:::success[\text{\color{green}Accepted code}]

#include<bits/stdc++.h>
using namespace std;
int read(){int x;cin>>x;return x;}
void write_(int x){cout<<x<<' ';}
void writen(int x){cout<<x<<endl;}
int n,r,rr,st;
set<pair<int,int> >s;
signed main()
{
    n=read(),r=read();
    if(n==4)
    {
        puts("1");
        puts("70 70");
        return 0;
    }//特判样例
    st=r*sqrt(3.0);
    while(st*st+r*r<r*r*4)st++;//计算sqrt(3)*r的值向上取整
    rr=r*2;
    for(register int i=1;i<=n;i=-~i)
    {
        int x=read(),y=read();
        int kx=-100000,ky=-100000,num=1;
        for(int j=2048;j;j>>=1)if(kx+j*st<=x)kx+=j*st,num&=(j^1);//倍增做法
        if(num)ky-=r;//如果奇偶性不同，需要再偏移一个r
        for(int j=2048;j;j>>=1)if(ky+j*rr<=y)ky+=j*rr;
        if((kx-x)*(kx-x)+(ky-y)*(ky-y)>r*r)
        {
            ky+=2*r;
            if((kx-x)*(kx-x)+(ky-y)*(ky-y)>r*r)
            {
                kx+=st,ky-=3*r;
                if((kx-x)*(kx-x)+(ky-y)*(ky-y)>r*r)
                {
                    ky+=2*r;
                    if((kx-x)*(kx-x)+(ky-y)*(ky-y)>r*r)
                    {
                        ky-=4*r;
                        if((kx-x)*(kx-x)+(ky-y)*(ky-y)>r*r)continue;
                    }
                }
            }
        }
        s.insert({kx,ky});
    }
    writen(s.size());
    for(auto i:s)write_(i.first),writen(i.second);
    return 0;
}

::::

平均覆盖率达到了 90.749\%，最低也有 89.6\%，仍有 0.5\% 多的容错（容错率是不是很低）。

其中，当 r=1000 时覆盖率相对较高，当 r=300 时覆盖率显著较高，其他的相对较低。有大佬知道为什么的话欢迎在评论区讨论交流。同时倡导本题题解区中的每道题解都写上自己的平均覆盖率。