GridPointsOnCircle
SRM 260 · 2005-08-27 · by gepa
Problem Statement
You will be given rSquare, the square of the radius of a circle. You are to return the number of lattice points (points with integer coordinates) that lie on the circumference of a circle with this radius centered at the origin of the (cartesian) coordinate system.
Constraints
- rSquare will be between 1 and 2,000,000,000, inclusive.
1 Returns: 4
A circle with radius 1 centered at the origin goes through 4 lattice points: (1,0), (0,1), (-1,0) and (0,-1).
25 Returns: 12
A circle with radius 5 goes through the points (+/-3, +/-4), (+/-4, +/-3), (0, +/-5) and (+/-5, 0) (12 points).
3 Returns: 0
No lattice point is at distance sqrt(3) from the origin.
12 Returns: 0
44 Returns: 0
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GridPointsOnCircle with a public method int countPoints(int rSquare) · 72 test cases · 2 s / 256 MB per case