CareerCup

For each possible center, compute the possible distances and sort them. Keep track of the count the value that is repeated most for that given center.

Pick the center with the maximum count.

O(n^2 log n).

let us say a point x,y lies on circle with centre x0,y0, we can say that a=x-x0,b=y-y0 lies on circle with centre 0,0.
now a^2+b^2=r^2. hence for each point x,y calculate x^2+y^2, and hash it to a table with this index and maintain count.
Now the entry with maximum count is answer. Complexity O(n)

Hi buddy, can you please share your interview experience along with the questions. Thanks

Here is my answer to this question. We can solve the problem with O(N^2) time complexity.

basicalgos.blogspot.com/2012/04/42-find-minimum-radius-that-covers-all.html

We can create a point class with x,y coordinate and hashmap<integer,arraylist<point>> this will give us the most common distance for each point then we can iterate to get the point with max number of points which satisfies the above criteria. We can maybe add a little optimization in running time if we can have a one more hashmap<point,hashmap<point,distance>>. So one we compute a distance between two pints we can add it to above map once for each of the points between which we just computed the distance. This way we can avoid calculating the distance again and again and we just look it up in the above map.

If for every point we create a map of the following structure :
<distance, count>

where distance is the distance of this point from another point in the plane. If two points A and B are equidistant from the same point P, then they must both lie on a circle with centre P and passing thru both these points A and B. The count gives us how many points are at a particular distance from point P.

Once we have computed this for every point, we then need to find the distance with maximum count. That point will be the centre and distance will be the radius.

In order to avoid repetitive updation for same set of points, we can update the hashtables of both points at the same time. For example, if we are calculating distance between A and B, we can update hashtables of A and B simultaneously.

I have not tested this yet but I think it should work. I hope I am not missing out anything.

<code>//Find the centre and radius of a circle which passes through the maximum number of points. The centre must be one out of the given N points.
#include<stdio.h>
#include<math.h>
#define n 14

float dist(int *a,int *b)
{
float d;
d = sqrt(((*(b+1) - *(a+1)) * (*(b+1) - *(a+1))) + ((*(b) - *(a)) * (*(b) - *(a))));
return d;
}

float max_occurence(float a[],float *val)
{
int i,j;
float occ[n] = {0},max,v[n]={0};

for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
if(a[i]==a[j])
{
occ[i]++;
v[i] = a[i];
}
}
}
max = occ[0];
for(i=0;i<n;i++)
{
if(occ[i]>=max)
{
max = occ[i];
*val = a[i];
}
}
return max;
}

float maxi(float d[])
{
int i,max = d[0],index;
for(i=0;i<n;i++)
{
if(d[i]>max)
{
max=d[i];
index=i;
}
}
return index;
}

void findcircle(int *a)
{
int i,j,c1=0,c2=0,index;
float r = 0, d[n]={0},temp[n]={0},val,radius[n]={0},tmp;
for(i=0;i<(2*n);i=i+2)
{
c2=0;
for(j=0;j<(2*n);j=j+2)
{
r = dist(a+i,a+j);
printf("Dist between (%d,%d) and (%d,%d) is %f \n",*(a+i),*(a+i+1),*(a+j),*(a+j+1),r);
temp[c2] = r;
c2++;
}
d[c1] = max_occurence(temp,&val);//finds the distance of all points from all the other points and find maximum occurence of distances
radius[c1]=val;
c1++;
}
index = maxi(d);
printf("Center of circle is (%d,%d)\n",*(a+(2*index)),*(a+(2*index)+1));
printf("Radius of circle is %f\n",radius[index]);
printf("Points on circle are:\n");
for(i=0;i<(2*n);i=i+2)
{
if(i!=(2*index))
{
tmp = (*(a+(2*index)) - *(a+i))*(*(a+(2*index)) - *(a+i)) + (*(a+(2*index)+1) - *(a+i+1))*(*(a+(2*index)+1) - *(a+i+1));
if(fabs(tmp - (radius[index]*radius[index])) <= 0.001 )//for floating point comparison
printf("(%d,%d)\n",*(a+i),*(a+i+1));

}
}
}

int main()
{
/*int a[n][2] = {{2,3},
{3,2},
{2,2},
{5,5},
{1,2},
};*/
int a[n][2] = {{2,4},
{3,3},
{3,5},
{4,2},
{4,4},
{4,6},
{5,3},
{5,5},
{6,4},
{2,2},
{2,3},
{3,2},
{3,4},
{4,3}
};
findcircle(&a[0][0]);

return 0;
}
</code>