给定 N 个相等的圆（可能重叠）和平面上的 M 个点。找到包含最大点数的圆

Question

下图是一个简单的案例。圆圈 1 获胜，因为它包含点数 [1, 2, 5] -- 比任何其他圆圈都多。

根据每个圆圈检查每个点的天真实现给出了时间限制。他们说“使用哈希”。但是在哪里呢？

#include <iostream>
#include <vector>

using namespace std;

struct Point
{
    int x;
    int y;
};

int64_t dist(Point p1, Point p2)
{
    int64_t dx = p1.x - p2.x; 
    int64_t dy = p1.y - p2.y;
    
    return dx*dx + dy*dy;
}

int main() 
{
    int circle_num;
    cin >> circle_num;
    
    vector<Point>   circles(circle_num);
    vector<int64_t> count  (circle_num);
    
    for (Point& p : circles)
        cin >> p.x >> p.y;
        
    int points_num;
    cin >> points_num;

    while (points_num--)
    {
        Point p;
        cin >> p.x >> p.y;
        
        for (int i = 0; i != circle_num; ++i)
        {
            if (dist(p, circles[i]) <= 400)
                ++count[i];
        }
    }
    
    int     index     = 0;
    int64_t max_count = 0;
    
    for (int i = 0; i != circle_num; ++i)
    {
        if (count[i] > max_count)
        {
            max_count = count[i];
            index     = i; 
        }
    }
    
    cout << (index + 1) << endl;
}

可能的输入：

3 // number of circles
-1 0 // circle 1 center
1 0  // circle 2 center
2 5  // circle 3 center
3 // number of points
10 0 
20 0
22 5

输出：3 -- 圆 3 包含的点数最多

Answer 1

由于圆都是一样大的（800个单位），一个实用的做法是把平面分成一个格子，每个方格401x401个单位，然后用一个hash from (x,y) -> list to收集每个方格中的点。

然后对于每个圆，只需检查它重叠的最多 9 个正方形中的点。

给定 N 个相等的圆（可能重叠）和平面上的 M 个点。找到包含最大点数的圆

Given N equal circles (possibly overlapping) and M points on a plane. Find a circle which contains maximum number of points

algorithm

hash