Cool Problem

circleproblem.txt

Given an array of N points in a plane, find the circle which contains the maximum numbers of the given points on its perimiter.
 
for each pair of points {                                               // O(N^2)
  for each of the N-2 remaining points {                                // O(N)
    compute radius and center of circle defined by the 3 chosen points
  }
  sort list by radius                                                   // O(N*log(N))
  filter list by (most common radius) and (most common center)          // O(N)              ? is it O(N)?
  return (radius, center x, center y, number of matching circles);
}
 
complexity is O(N^3*log(N))