A simple C++ algorithm to count the point in circle.

#programming #cpp #algorithms #beginners

1.Introduction

Now I'd like to introduce an algorithm called "Bingxi's Fish Algorithm", here is the statement.

There are two-dimensional coordinate systems with x abscissa and y ordinate, BingXi's fish are distributed in the coordinate system, with a maximum of one fish per coordinate point. Let Bingxi's radius of influence be r, and the fish in this circle will become Bingxi's fish. When asked where BingXi was, he can get the largest number of fish.

2.Analysis

This problem is a single algorithm problem, which can be solved by enumeration. Start with the coordinates of each fish and check them one by one, and the method is as follows:
Step 1: Approximate positioning
Take the coordinates of each fish as the center of the circle, and R as the radius to make a circle, and record the coordinate points contained in the circle.
Step 2: Precise positioning
Make a circle with radius r around each circle position, and the range of the circle should contain the coordinates of the fish, the actual operation is to make a circle with radius r with the coordinate point in the circle as the center point of the circle and find out the circle that contains the most fish, the center coordinate of the circle is the one sought (there may be more than one coordinate that meets the conditions)

Now let's have a look of the algorithm requirements.

Input
The first line, a positive integer r, represents Bingxi's radius of influence.
The second row, a positive integer n, indicates the number of fish.
The next n rows, each with two values of x1 and y1, indicate the position of the fish in the coordinate system.

Output
Condition 1: There is only one matching coordinate.
Outputs the x, y values of the coordinates, as well as the number of fish that can be obtained.
Condition 2: There is more than one matching coordinate.
In the first row, the number of fish that can be obtained m
In the second row, the number of coordinate points z.
In the next z row, the x,y values of each coordinate point are output.

Numerical range
x∈[0, 2147483647], y∈[0, 2147483647], r∈[2, 10000], x, y, r∈N

3.Code design

Preparation

struct Fish //the stucture of the fish
{
    int x;
    int y;
};

Fish fish[100010]; //fish point
Fish Point[100010]; //The point of the answer

int num = 0; //the number of the "Point"
int sum = 0; //the fish number in the circle
int point_num = -1; //the max fish value that can get.
bool Repeat = false; //to ensure wether the answer point is repeated or not

Input

int r;
cin >> r;
int n;
cin >> n;
for (int i = 1; i <= n; i++) //input the fish point
{
    cin >> fish[i].x;
    cin >> fish[i].y;
}

Processing

for (int i = 1; i <= n; i++) //all of the fish point
{
    //find the fish point in circle
    for (int j = fish[i].y - r; j <= fish[i].y + r; j++) //y
    {
        if (j < 0)
        {
            continue;
        }
        for (int m = fish[i].x - r; m <= fish[i].x + r; m++) //x
        {
            if (m < 0)
            {
                continue;
            }
            int dis = (fish[i].x - m) * (fish[i].x - m) + (fish[i].y - j) * (fish[i].y - j);
            if (dis <= r * r)
            {
                //Make a circle with the inner point of the circle as the center of the circle, and record the number of coordinate points in the circle
                sum = 0;
                for (int p = 1; p <= n; p++)
                {
                    int di = (fish[p].x - m) * (fish[p].x - m) + (fish[p].y - j) * (fish[p].y - j);
                    if (di <= r * r)
                    {
                        sum++;
                    }
                }
                if (sum > point_num)
                {
                    point_num = sum;
                    num = 0;
                    num++;
                    Point[num].x = m;
                    Point[num].y = j;
                }
                else if (sum == point_num)
                {
                    for (int i = 1; i <= num; i++)
                    {
                        if (Point[num].x == m && Point[num].y == j)
                        {
                            Repeat = true;
                        }
                    }
                    if (Repeat == false) //to judge if repeat
                    {
                        num++;
                        Point[num].x = m;
                        Point[num].y = j;
                    }
                    else
                    {
                        Repeat = false;
                    }
                }
            }
        }
    }
}

Output

if (num == 1)
{
    cout << Point[num].x << " " << Point[num].y << " " << point_num;
}
else if (num > 1)
{
    cout << point_num << endl;
    cout << num << endl;
    for (int i = 1; i <= num; i++)
    {
        cout << Point[i].x << " " << Point[i].y << endl;
    }
}
else
{
    cout << "error";
}