I was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:\n\nThere\'s a list of (x,y) points and a method `getCircle` with the following signature:\n```\n/**\n * Given three points returns a circle (Radius, and center) such that all three points lie in its circumference\n * or it returns null if no such circle is possible.\n */\nCircle getCircle(point1, point2, point3);\n```\n\n`getCircle` method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.\n\nThe obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?\n\n

I was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:\n\nThere\'s a list of (x,y) poin