Picture below shows a simple case. Circle 1 is the winner, because it contains points [1, 2, 5] -- more then any other circle.

Naive implementation which checks every point against every circle gives Time Limit. "Use hash" they say. But where?

#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;
}

Possible input:

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

Output: 3 -- circle 3 contains the most number of points

CodePudding user response：

Since the circles are all the same size (800 units), a practical approach is to divide the plane into a grid, with each square 401x401 units, and use a hash from (x,y) -> list to collect the points in each square.

Then for each circle, just check the points in the up to 9 squares that it overlaps.