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).
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
Hope this helps