May Long (WTBTR)

I really didnt get that where I am getting wrong in this question.
My approach would be if any two points lie on same line then the answer would be 0 but if they dont then it is just find two closest points in given 2d and then find the distance between them and then distance/2 will be the answer but I am getting different answer when i am run input on accepted solution and my solution .I really didnt get where I am getting wrong so please anyone …
thankyou
question link - https://www.codechef.com/MAY19B/problems/WTBTR

Or just share your approach it helps me to understand better.

I will give you an example where your approach fails. Say there are 3 points (0,0), (10,0) & (0,11). The answer should be 0.5 as we can draw a line passing through (0,0) and the other with slope -1 passing through the points (10.5,0) & (0,10.5).
But your logic will give some wrong answer (probably 2.25) .

my approach : added lots of comments. Yes you were going in correct direction but slight mistaken, I used something similar

You can refer to my solution if still not clear ,It isn’t half the distance between two closest points.

https://www.codechef.com/viewsolution/24161413

I think he is not checking the -1 slope case.

y = mx+c ( you have to consider for m=1 and -1)@silent_killer1

Hope this helps!

1 Like

I used the following algorithm to find the answer:

  1. For each pair of points, determine the equation of a line with a positive slope of 1 through one of the lines. This is basic geometry.
  2. Next compute the distance from the other point to this line (this distance is perpendicular to the line drawn through the first point). This equation is not as basic as the one for drawing the line, but you can readily find it on the web by searching for “distance between a point and a line”.
  3. The distance computed should be halved, since the line would need to be between the two points in order to determine the minimum for these two points.
  4. You must also do the preceding steps for the negative slope line.
  5. The answer will be the minimum of the answers from all of the cases.

You will find that all of the distances computed will involve a denominator containing the square root of two, but since the minimum distance is to be multiplied by the square root of two, this minor mathematical inconvenience is avoided. The correct answers will be integers or will end with 0.5, but for some reason the answers will be marked incorrect if they are not written in decimal form (despite the fact that the example had an answer in integer form).

4 Likes

See i have a simple approach just rotate the axis by 45 degree …question becomes very simple now
1 sort the points with respect to x-axis and then find the pair of points with shortest distance .Pass a line parallel to y-axis in b/w the pair of points i.e max of the min dist along x-axis is this distance/2
2. do the same along y-axis

find the min of the two min in step 1 and 2 and it will be the ans

4 Likes

Can anyone share with his Java solution please? Here is mine, that has O(n * log n) complexity, and I don’t know how to improve it further:
https://www.codechef.com/viewsolution/24258881

@dzmitry_alifer bruh, you can filter accordingly in all submissions and can view anybody soln (after the contest)
here is the link to the page

I was doing the same thing. but i got only 10 points and rest were TLE.

In fact your solution has complexity of O(n^2), because solve has double cycle over the vector p. You can reduce it multiple ways, as mentioned by others. The method I used, is to calculate “new coordinates” for the points according to which line of slope 1/-1 they are on. It can be done by checking where that given line meets the axis. This way the new coordinates can be x+y and x-y. After that you only have to check whether there are any duplicate of new coordinates (any of them). With sorting in O(n*log(n)) you can find it out.
E.g. you have point (2,2) and (1,1). The new coordinates are 4 (the point is on the x+y=4 line) and 0 (the point is on the x-y=0 line) for (2,2) and 2 and 0 for (1,1). They have the common coordinate of 0 for the second coordinate, which means both on the line x-y=0. In case there are no duplicates you, can find the minimum difference easily from the sorted values.

I hope I could help.

1 Like

Yep, you’re right! Thx for the brilliant explanation!

same with me bro… i did in pyhton

As far as approach is considered , it can be solved in two ways:-

Method 1 :- take equation of line to be y = mx + c , m= +1 , -1 , therefore it further reduces to
y = x + c , y =x-c . make two separate arrays for the constant c one for slope=1 line
and slope =-1 line by substituting input points in equation of line.
Observations : -
1.) if in any array for constant c , there are two identical c then answer is 0 as the
lines become identical meaning a single line can pass through these points. Now
we are left with N-2 points and N-2 lines which means every point is on line
hence a = 0.

                     2.) if point 1 is not satisfied , then N-2 lines can be drawn through N-2 points , we are left with two points we
                           intend to find points with smallest distance between them and passing a line 
                            through the centre of them , suppose for point 1 and point 2 the value of c is
                            c1 and c2 then minmum distance points would be for which c1 - c2 is minimum.
                             Once appropriate points are known just calculate the required distance by 
                             finding distance of points from the line passed through midpoint of two points.
                             take the smallest distance. 

                     3.)Through the c1 - c2 thing time complexity is reduced as you would not be 
                         bruteforcing and calculating distance between every two points.

Method 2 : - I solved it using this one. There is something called the Manhattan distance , and
45degree norm. As we can see that all our lines are oriented at an angle of 45 degree
+135 degree(-45 degree).

                    Observation:-
                     1.)As one user has mentioned rotation of axis by 45 degrees but how will this help? 
                     What this does is it simplifies the calculation hugely. if I rotate my axis by 45 degree
                     clockwise then all my lines become horizontal and vertical lines of type y=c or x =c 
                     where c is some constant.

                     2.) transform all points for 45 degree clockwise rotation by these equation:-
                       xTransformed = (yInput + xInput / sqrt(2)) , yTransformed = (yInput - xInput / 
                       sqrt(2)) . sqrt(2) can be ignored for obvious reasons. Store them at time of input as
                       some x[] and y[];

                      3.) if for any two x in x[] x1 -x2 == 0 then answer is azero. Why? this means that x1 = 
                           x2 hence a vertical line can pass through it. Remember all our lines have 
                           transformed to horizontal and vertical lines :) . now we are left with N-2 points 
                           and N-2 lines hence all points are on same line. Answer is still zero if y1 - y2 == 0 
                           for any two y in y[] using above arguments.

                       4.) when answer is not zero we have to find two points having minimum distance 
                            between them as for others N-2 lines can pass through other N-2 points. now 
                            since we can make a horizontal and vertical line , we require minimum 
                            horizontal or minimum vertical distance between points , we take smaller one 
                            and divide it by 2 to get our answer as this would be equivalent to drawing a 
                            line at mid point.

Though method 2 has more points of explanation but I can guarantee you it is the easy way out. Read about manhattan distance and line sweep algorithms to get an Idea how this question was actually framed.

Just visualize how problem becomes/changes after 45 degree rotation all these points will start making more sense. Check my solution for more help! https://www.codechef.com/viewsolution/24229036
It is not in the best commented fashion but still bearable :slightly_smiling_face:

Hope this helps :smile:

5 Likes

I also did in python. Can you send me your submission?

The enhancements to the basic method that I previously outlined are:

  1. If you consider the straight line equation and the distance from a point to that line, you can come to the conclusion that the equations reduce to basic factors b-a and b+ a (where the input point is (a,b).
  2. Store the b-a factor in a vector and sort into ascending order. The absolute difference of the two smallest numbers in the sorted vector is twice the distance of the point to the line for one of the slopes (there is also a square root of two in the denominator but this is cancelled out since the problem states that that answer is to be multiplied by the square root of two).
  3. Store the b+a factor in another vector and sort into ascending order. The absolute difference of the two smallest numbers in the sorted vector is twice the distance of the point to the line for the other slope (there is also a square root of two in the denominator but this is cancelled out since the problem states that that answer is to be multiplied by the square root of two).
  4. The smaller of the numbers calculated in steps 2 and 3 divided by two is the answer.

Okay bro you are very smart

https://www.codechef.com/viewsolution/24279954

This is my implementation. I implemented it using your first described method and I’m getting a WA for tests 1,2 of sub-task 1.
Can you please help.
Thanks in advance

Hey Joel! I went through your code and even tried to change a few things to get it accepted , however could not get your test cases passed. As far as approach is considered I think you have implemented it correctly as you are able to clear the 90 points subtask. One think that I found odd was in the last step. The general equation of line is y+mx+c = 0 if you compare in your last step one of your lines would not follow that. I tried changing it but it didn’t fare well , perhaps I am not able to completely understand your code. Please try that otherwise look for maybe some small error causing the trouble. At the end of day method 2 is not bad either :smile: Let me know if you could figure something out otherwise you can contact one of my friend who actually coded using exact method 1 approach.

Great explanation :D!
Could you explain why sqrt(2) is ignored when rotating co-ordinates?