sorry but I will rewrite this so it's more clear.tan_Yui wrote:My algo is here.jaracz wrote:how to compare all pairs faster than O(n^2) it gives TLE of course

1) Sort data in ascending order based on x coordinates.

2) Set default minimum distance d(d is distance between point1 and point2.

3) Restrict the x-range with d.

4) Copy 1) between x-range of 3).

5) --Sort 4) in ascending order based on y coordinates.

6) --Restrict the y-range with d.

7) --Measure the distance -> new_d.

--Update d if new_d is smaller than d.

9) Back to 3).

This algorithm can be see in this site.

The point of this algorithm is to reduce the number of times of measuring the distance.

Best regards.

this is called the sweep plane algorithm.

1) Sort the points according to x using a !!!!!!O(nlog(n))!!!!! algorithm.

So the relationship between the points can be identified. We call this sorted list of points S.

2) Divide the points into two groups according to their x-value using the x-vaule of the median of S. We call the two groups S1 and S2. Now using x-vaule of the median of S might not be best in some situations, but in this problem with unknown inputs, it's fine. (DO NOT physically divide them. How to do you do this then? Look at the index of the median you will see a hot blonde chick... or dude... *shivers*, whichever you prefer.)

3) Find the minimum distances between 2 points in each of the two groups by recursion using these steps. we will call them d1 and d2. The recursive method will back track when of course, there's only 3 points or less in the current S we are looking at. We return minimum distance within this no-more-than-3-vertices graph using brute force.

4) And d3 will be the minimum distance between any two points in S such that one point come from the first group and the other point come from the second group. This must be done using special methods or else you will still end up with a O(n^2) or worst if you use brute force. One of them is described below.

----------------------------------------------------------------------------------

Since we know d1 and d2, and we must find the minimum of the distances, we take the lesser of the two, let's call it d12(Hey! Who says rappers can't be good at math. m'^-^'m), as a search limit when we are looking for d3.

a) We extract all points with its x-value within -d12 of the x-value of the median of S. we call it S1x.

b) We extract all points with its x-value within d12 of the x-value of the median of S. We call it S2x.

c) Sort S1x and s2x using each points' y-value.

d) For each point in S1x we find the minimum distance to S2x such that the the points we look at in S2x have a y-value that is within d12 range of S1x point's y-value. We will end up with a set of minimum distance.

e) Now we set d3 equal to the minimum of that set. And returns.

meow you can just operate on one list instead of S1x and S2x, which save you some memory, but seperating the list will help you on bookkeeping by getting rid of some if statments.

------------------------------------------------------------------------------------

5) The minimum of d1, d2 and d3 will be your answer.

Any fall through cases will set the minimum distance returning to Max distance, which is given in the problem.

note: Think a little about how the algorithm works before you start coding will help you a lot. Maybe you'll find a better solution.