CropCircles
SRM 359 · 2007-07-21 · by bmerry
SRM 359 · 2007-07-21 · by bmerry · Brute Force, Geometry
Problem Statement
Problem Statement
Making a crop circle is a difficult job because it is hard to see what one is doing. You have found a farm with boulders scattered around, and have realised that it would be easiest to use a circle that passes through three or more of the boulders.
You have started wondering how many different circles you could produce in this way. Given int[] x and int[] y, return the number of distinct circles that can be made. The boulders are at (x[0], y[0]), (x[1], y[1]), etc.
Notes
- The field is large enough that a circle can be made through any three boulders that do not lie in a straight line.
- When four or more boulders lie on the same circle, this circle should still only be counted once.
Constraints
- x and y will each contain between 1 and 50 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x and y will be between 0 and 500, inclusive.
- No two boulders will be in the same location.
Examples
0)
{1, 2, 1, 2, 8}
{2, 1, 8, 9, 9}
Returns: 1
The five points all lie on a common circle.
1)
{0, 4, 7}
{3, 3, 3}
Returns: 0
The three points lie on a single line, so there is no circle that passes through them.
2)
{0, 10, 10, 10, 20}
{10, 0, 10, 20, 10}
Returns: 5
3)
{0, 10, 11, 10, 21}
{10, 0, 11, 20, 10}
Returns: 10
4)
{291, 321, 430, 475}
{469, 449, 346, 281}
Returns: 1
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CropCircles with a public method int countCircles(vector<int> x, vector<int> y) · 60 test cases · 2 s / 256 MB per case