EnclosingSquare
TCO10 Final · 2010-04-11 · by lyrically
TCO10 Final · 2010-04-11 · by lyrically · Math
Problem Statement
Problem Statement
Find the area of the minimum square in the plane,
such that its 4 vertices are distinct lattice points
and there are exactly n lattice points strictly inside it.
If there is no such square, return 0 instead.
Notes
- A lattice point in the coordinate plane is a point whose x-coordinate and y-coordinate are both integers.
Constraints
- n will be between 0 and 1,000,000,000,000, inclusive.
Examples
0)
4 Returns: 5
The square below contains exactly 4 lattice points strictly inside itself and has an area of 5.
1)
3 Returns: 0
There is no such square.
2)
1000000000000 Returns: 1000000000001
3)
101 Returns: 104
4)
0 Returns: 1
Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EnclosingSquare with a public method long long getMinimum(long long n) · 101 test cases · 2 s / 256 MB per case