Programming exercises: whole point and circle (solution ideas and code implementation)

【 Problem description 】

Given in a plane rectangular coordinate system n On the hour , Take each integral point as the center of the circle , Draw a radius of r The circle of , Please find out which integer point is the center of the circle and the circle contains the most integer points , Output this value .
【 Input form 】

Enter two integers on the first line n and r, Respectively represent the number of integral points and the value of radius

Next n Enter two integers per line x,y, They represent the abscissa and ordinate of the whole point respectively
【 Output form 】

Output in the given n Draw a radius of... For the center of the circle at a certain point in the whole point r The maximum number of integer points that can be contained in a circle of
【 The sample input 】

3 2

0 0

0 2

2 0
【 Sample output 】

3
【 Sample explanation 】

With (0,0) This point draws a radius for the center of the circle 2 The circle of , Can contain 3 A little bit

And then (0,2) or (2,0) Draw a radius for the center of the circle 2 The circle of , Can only contain 2 A little bit

Therefore, it can contain at most 3 On the hour
【 Standard for evaluation 】

about 100% The data of , Guarantee -1e9<=x,y<=1e9,1<=r<=2e9

about 40% The data of , Guarantee 1<=n<=100

about 100% The data of , Guarantee 1<=n<=5000

title

The data range of points is not large , Square enumeration can solve
Note that the calculated distance will explode int, Need to open long long Carry out operations
utilize pair Storing point coordinates is more intuitive

Code implementation

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef pair <long long , long long > PLL;
vector <PLL> s;
int n;
long long r;

int main()
{
    
    cin >> n >> r;

    for (int i = 0; i < n; i ++)
    {
    
        long long x, y;
        cin >> x >> y;
        s.push_back({
    x, y});
    }
    int res = 0;

    for (int i = 0; i < n; i ++)
    {
    
        int temp = 0;
        for (int j = 0; j < n; j ++)
        {
    
            // Whether the integer operation will explode int
            if((s[i].first - s[j].first) * (s[i].first - s[j].first) + (s[i].second - s[j].second) * (s[i].second - s[j].second) <= r * r)
            {
    
                temp ++;
            }
        }
        res = max(res, temp);
    }

    cout << res;
    return 0;
}