sort p(xi,yi) on the basis of x-axis. find media of x-axis = x_median
sort p(xi,yi) on the basis of y-axis. find media of y-axis = y_median
find distance from p(x_median,y_median) to all N points.
the distance minimum from p(x_median,y_median) is the point closest point.
algo seems to work , but not checked all test cases.
On Wed, May 9, 2012 at 3:27 PM, Nima Aghdaii <nima.aghd...@gmail.com> wrote:
> Wait! Let's clarify things before shooting random guesses.
> First of all, which norm is used for distance?
> I'm assuming that it is L2 norm (Euclidean distance).
> The problem statement clearly mentions that the answer should be one of
> the given points. So, I don't see any rationale behind taking the mean!
>
> The idea of binary search is also wrong. The function is obviously not
> convex. Norm itself is convex but summation is not a convex preserving
> operator. You can easily verify that. However Max is a convex preserving
> operator. So, if the problem was finding the point which minimizes the Max
> distance, we could use binary search.
> The idea of MST is way out of this topic! Common! MST might have made
> sense if we were talking about distances on the graph. and then what?
> Finding the centroid? centroid, eccentricity,... are just based on
> connectivity. They don't even take into account the distances!
> Talking of "median"... please define it first. Or just explain how you
> could even sort 2D points!
>
> --Nima
> On May 8, 2012 10:04 PM, "pacific :-)" <pacific4...@gmail.com> wrote:
>
>>
>>
>> On Tue, May 1, 2012 at 8:44 PM, Bhupendra Dubey
>> <bhupendra....@gmail.com>wrote:
>>
>>> Find the centroid
>>>
>>> X= (x1 +x2....xn)/N
>>> Y=(y1+y2......yn)/N
>>> This will precisely be the point no need to calculate and check with
>>> distance.
>>>
>> @dubey : Consider this case, let there be a cluster of 4 points near the
>> origin and 1 point at (100,0). Then the answer would be near the origin and
>> not close to the centroid. "median" might make some sense.
>>
>>>
>>>
>>> On Tue, May 1, 2012 at 1:18 PM, mohit mishra <mohit7mis...@gmail.com>wrote:
>>>
>>>> Let me know if there is any bug
>>>> /*using centroid of plane */
>>>>
>>>> struct point
>>>> {
>>>> int x;
>>>> int y;
>>>> };
>>>> typedef struct point Point;
>>>> int main()
>>>> {
>>>> int n,i;
>>>> int d,dis;
>>>> float sum_x=0,sum_y=0;
>>>> Point centroid,final;
>>>> //clrcsr();
>>>> printf("how many points? ");
>>>> scanf("%d",&n);
>>>> Point p[100];
>>>> printf("enter X and Y cordinates of %d points\n",n);
>>>> for(i=0;i<n;i++)
>>>> scanf("%d%d",&p[i].x,&p[i].y);
>>>> for(i=0;i<n;i++)
>>>> {
>>>> sum_x=sum_x+p[i].x;
>>>> sum_y=sum_y+p[i].y;
>>>> }
>>>> centroid.x=(int)sum_x/n;
>>>> centroid.y=(int)sum_y/n;
>>>> for(i=0;i<n;i++)
>>>> {
>>>> dis=distance(centroid,p[i]);
>>>> if(dis<d)
>>>> {
>>>> d=dis;
>>>> final.x=p[i].x;
>>>> final.y=p[i].y;
>>>>
>>>> }
>>>> }
>>>> printf("\n The point is (%3d ,%3d)",final.x,final.y);
>>>> getch();
>>>> return 0;
>>>> }
>>>> int distance(Point A,Point B)
>>>> {
>>>> int x,y;
>>>> x=(A.x-B.x)*(A.x-B.x);
>>>> y=(A.y-B.y)*(A.y-B.y);
>>>> return sqrt(x+y);
>>>> }
>>>>
>>>>
>>>> On Mon, Apr 30, 2012 at 4:34 PM, kosgi santosh
>>>> <santoshko...@gmail.com>wrote:
>>>>
>>>>> how can we find centriod of n points in a plane?
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Regards,
>>>>> Santosh K.
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> bhupendra dubey
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> regards,
>> chinna.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
