Re: Mini-challenge: HHC2012 RPL programming contest with larger input Message #9 Posted by C.Ret on 1 Oct 2012, 4:30 p.m., in response to message #8 by David Hayden
Ah!Ah! That's a much clever algorithm!
As soon as P1 and P2 point are established, a large majority of points in the middle of the circle area will be discarded from the processing list, making the further steps much more efficient.
Following is just illustrations of the algorithm: since 1000 elements is a big bunch of points, I will represent this among as an array of dots:
1.1 - Convert the list to a list of complex numbers.
1.2 - Take the first point on the list and find the point furthest from it. Call this point p1. This is a point "near the outside"
1.3 - Now find the point furthest from P1. Call this P2 and note the distance from P1 to P2.
1.4 - Now comes the important part. Draw a circle with p1 and p2 as the diameter.
1.5 - For each point outside the circle, find the furthest point from it.
1.6 - If the distance between them is greater than the distance between P1 and P2, then replace P1, P2 and dist with the new values.
2.4 - Draw a circle with p1 and p2 as the diameter.
2.5 - For each point outside the circle, find the furthest point from it.
2.6 - If the distance between them is greater than the distance between P1 and P2, then replace P1, P2 and dist with the new values.
3.4 - Now comes the important part. Draw a circle with p1 and p2 as the diameter.
3.5 - For each point outside the circle, find the furthest point from it.
3.6 - If the distance between them is greater than the distance between P1 and P2, then replace P1, P2 and dist with the new values.
3.7 - When you're done, P1 and P2 are the furthest points and dist is the distance between them.
Yeh! Now I have to find a way to implement this into an HP-28S !
|