BestCircle
SRM 123 · 2002-12-10 · by axchma
Problem Statement
Given a set of points on a plane with x/y integer coordinates between -100 and 100 inclusive and an integer radius, determine the maximum number of these points a circle with the given radius can cover. (For the purposes of this problem, a circle covers a point if and only if the point is inside or exactly on the border of the circle).
Notes
- The center of the circle need NOT be at a point with integer coordinates.
- xCoor and yCoor are lists of x coordinates and y coordinates of the given points in the same order.
Constraints
- xCoor contains between 1 and 50 elements inclusive
- yCoor contains the same number of elements as xCoor
- each element of xCoor and yCoor is between -100 and 100 inclusive
- radius is between 1 and 150 inclusive
{1,1,5,5}
{1,5,1,5}
2
Returns: 2
These points are the vertices of a square. The best possible place for the center of a circle with radius 2 is in the middle of an edge.
{1,1,4,4}
{1,4,1,4}
3
Returns: 4
These points are the vertices of a square. The best possible place for the center of a circle with radius 3 is in the center of the square.
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,
43,44,45,46,47,48,49,50}
24
Returns: 49
{1,1,1,3,3}
{1,3,5,1,5}
2
Returns: 3
{-100,1,100}
{-100,1,100}
150
Returns: 3
{0,0,5,5}
{0,5,0,5}
4
Returns: 4
These points are the vertices of a square
{0,0,100,-100,1}
{100,-100,0,0,100}
100
Returns: 4
personal comment: the difference between answer 4 and 5 is .005
{-100,-95,-64}
{-100,-54,-60}
27
Returns: 2
personal comment precision 10^-5
{-91,-91,-45,7,-2,95,-15,-61,-9,-18,-72,46,-79,0,-28,-28,-50,91,59,-4,-18,-32,23,-15,59,-4,22,-48,-57,-29,87,-32,-7,-3,40,-26,-28,93,14,67,37,73,-64,-28,42,-11,-47,-95,24,63}
{1,-92,25,38,33,-12,63,-30,19,19,39,-31,-95,56,-85,-31,58,77,46,-89,-18,-48,25,-8,13,21,14,-78,-1,-22,-10,-62,79,39,-35,-83,-6,56,4,-39,-33,95,16,-32,-88,-26,67,-5,26,-92}
84
Returns: 39
twenty random test cases for you
{38,-60,20,98,74,-28,21,-8,48,0,-22,88,99,-32,-47,74,-84,-33,-60,66,46,6,88,61,-2,-8,42,0,-87,4,-14,-33,-47,75,66,-83,0,95,5,55,-47,-6,92,4,-83,79,-95,-26,11,79}
{67,-50,-49,35,-13,52,-17,93,44,77,-8,-22,16,82,15,79,1,-48,-6,96,-66,-35,0,79,82,-34,-21,97,-76,54,-15,41,-68,-45,15,-54,75,-77,16,-31,-90,-68,75,-35,-17,7,-59,47,19,69}
145
Returns: 50
there are thousands more where 64-83 came from....
{95,-26,-49,76,14,-44,62,98,-81,-31,72,32,-65,20,-31,17,-90,-52,43,-98,-70,-24,-83,87,11,-97,84,-9,-15,-23,-49,56,70,71,64,66,-11,-6,-80,-71,45,65,-46,48,-63,63,68,89,-61,57}
{19,-86,-6,-40,-73,-67,-7,-81,18,-16,90,-9,21,73,74,-87,-15,37,36,-64,-8,-97,-2,58,61,68,52,99,21,-21,6,-98,95,-89,7,49,0,71,-50,50,44,-19,72,-93,-77,15,73,85,-87,46}
26
Returns: 8
here's a sample of 30 more...
{58,48,-76,100,95,89,22,75,5,98,6,-1,-86,84,65,11,70,82,88,-39,-43,-81,99,48,-5,-8,-9,92,10,-51,-31,-66,27,64,-18,-41,-37,-54,-76,74,-74,-86,32,84,9,-55,7,52,92,-90}
{50,-80,74,16,57,39,-25,75,49,-10,-28,47,-47,-20,56,69,15,43,-83,-8,-77,9,-21,14,92,74,-67,-44,-47,85,-12,58,-74,-83,89,-94,-69,-23,-68,6,76,-13,-46,-36,54,-78,54,41,-56,53}
148
Returns: 50
Shall I continue?
Submissions are judged against all 130 archived test cases, of which 12 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BestCircle with a public method int find(vector<int> xCoor, vector<int> yCoor, int radius) · 130 test cases · 2 s / 256 MB per case