2
\$\begingroup\$

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

enter image description here

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

enter image description here

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

  • \$1 <= points.length <= 100\$
  • \$points[i].length == 2\$
  • \$-10^4 <= points[i][0], points[i][1] <= 10^4\$
  • \$1 <= r <= 5000\$

Inputs

[[-2,0],[2,0],[0,2],[0,-2]]
2

[[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]]
5

[[-2,0],[2,0],[0,2],[0,-2]]
1

[[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]]
2

[[5738,-1857],[2264,1769],[5944,-9368],[3459,-9748],[8624,159],[985,-5051],[-8275,-9383],[7923,-591],[-8121,4781],[-9594,938],[-24,223],[9084,-4952],[-6787,5289],[4879,-4],[3998,369],[-7996,-7220],[-414,3638],[5092,4406],[1454,2965],[9210,-6966],[-4111,-8614],[4507,2213],[-4112,3699],[-9956,-2420],[7246,6775],[1164,5762],[6778,-5099],[-6655,-9514],[-2778,-7768],[6973,-7458],[7334,-1124],[4840,-8991],[941,5018],[1937,3608],[6807,6159],[763,1355],[-9776,-5074],[1107,1822],[-6779,-5400],[4219,-5674],[9823,-4630],[-9172,-7089],[-1875,162],[2267,1685],[4161,-1638],[-2475,9697],[-5367,-952],[-7786,4367],[839,1415],[8832,-4596],[-3843,7126],[-4242,8513],[-7883,1951],[9105,8342],[-4109,-4510],[1875,3149],[-7759,-6505],[1764,1624],[-6917,-6653],[-1438,6916],[-758,-3300],[3694,6699],[6135,2622],[7485,8284],[-9616,-8501],[408,4743],[8939,-731],[9208,-3748],[6059,-2587],[8403,4154],[2361,5708],[-3958,-3943],[-1746,-9082],[2864,-3231],[-4940,8519],[-8786,7898],[5154,-3647],[9011,8170],[-205,8717],[...
4411

Outputs

4
5
1
4
23

Code

#include <cstdint>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>

class Solution {
    static constexpr double precision = 1e-6;
    double R;

    static struct Point {
        double x;
        double y;
    };

    std::vector<Point> point;

public:
    std::int_fast32_t numPoints(
        const std::vector<std::vector<int>>& points,
        const std::int_fast32_t r
    ) {
    
        const std::size_t length = points.size();
        R = (double) r;
        point.resize(length);

        for (std::size_t len = 0; len < length; ++len) {
            point[len].x = points[len][0];
            point[len].y = points[len][1];
        }

        std::int_fast32_t max_darts = 1;

        for (std::size_t i = 0; i < length; ++i) {
            for (std::size_t j = 0; j < length; ++j) {
                if (i == j || getEuclideanDistance(point[i], point[j]) - 2 * R > precision) {
                    continue;
                }

                std::int_fast32_t curr_darts = 0;
                const auto center = getDartboardCenter(point[i], point[j]);

                for (std::size_t k = 0; k < length; ++k) {
                    if (getEuclideanDistance(point[k], center.first) - R < precision) {
                        ++curr_darts;
                    }
                }

                max_darts = std::max(max_darts, curr_darts);
            }
        }

        return max_darts;
    }

private:
    double getEuclideanDistance(
        const Point& a,
        const Point& b
    ) {
        return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2));
    }

    std::pair<Point, Point> getDartboardCenter(
        const Point& a,
        const Point& b
    ) {
        Point mid;
        std::pair<Point, Point> center;
        mid.x = (a.x + b.x) / 2;
        mid.y = (a.y + b.y) / 2;
        const double theta = std::atan2(a.y - b.y, b.x - a.x);
        const double temp_point = getEuclideanDistance(a, b) / 2;
        const double euc_dist = std::sqrt(std::pow(R, 2) - std::pow(temp_point, 2));
        center.first.x = mid.x - euc_dist * std::sin(theta);
        center.first.y = mid.y - euc_dist * std::cos(theta);
        // For optimization, later!
        center.second.x = mid.x + euc_dist * std::sin(theta);
        center.second.y = mid.y + euc_dist * std::cos(theta);
        return center;
    }
};

References

\$\endgroup\$
2
\$\begingroup\$

Don't change the API

The LeetCode problem gives you the public API:

int numPoints(vector<vector<int>>& points, int r)

Don't change int to int_fast32_t, since this might cause your function to become incompatible with what LeetCode expects. If you want to use int_fast32_t internally, that is fine.

Make functions that do not access member variables static

This applies to getEuclideanDistance().

Make functions that do not change member variables const

This applies to getDartboardCenter().

Naming things

It's one of the two hard things in computer science, along with cache invalidation and off-by-one errors.

Your function getDartboardCenter() does not in fact return the center of the dartboard. It just returns two guesses based on two input points. And only one element of the pair is ever used. Maybe getCandidateCenter() is a better name.

Also, temp_point is not a point, it is a distance, so name it temp_distance or temp_dist.

Use std::hypot()

The standard library already has a function for you that can help you calculate the euclidian distance: std::hypot(). So:

static double getEuclideanDistance(const Point& a, const Point& b) {
    return std::hypot(a.x - b.x, a.y - b.y);
}

But even better:

Avoid unnecessary floating point math

You have already noticed that floating point math is not infinitely precise. However, integer math is (as long as you don't exceed the maximum value an integer variable can hold). You can check if a given point with integer coordinates is within a circle centered at the origin with radius R by writing:

int R; // radius
int x, y; // point coordinates

if (x * x + y * y <= R * R) {
    // point x, y is inside the circle
}

There might be more math that can be done using integers.

Simplify your trigonometry

Given two doubles, dx and dy, and:

double theta = std::atan2(dy, dx);
double dist = std::hypot(dy, dx);

Then std::sin(theta) * dist == dy, and std::cos(theta) * dist == dx. This means that you didn't need to use these trigonometric functions at all, and could have written:

const double temp_dist = getEuclideanDistance(a, b);
const double euc_dist = std::sqrt(std::pow(R, 2) - std::pow(temp_dist / 2, 2));
const double scaled_dist = euc_dist / temp_dist;
center.first.x = mid.x - scaled_dist * a;
center.first.y = mid.y - scaled_dist * b;

This could be further simplified a bit.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.