Geometry problem. Help!

help
1

Part of the problem I am solving requires to minimize the sum defined below.

Given N points on a straight line. It is sure that all points lie on the line, and the line has a slope = 1). We have to choose 1 point among them and find the sum of distances of all other points from this point.
This sum should be the minimum.

problem link
I haven’t read the editorial, I thought of an approach but can’t apply it.

Any help would be great.

2

Every point lies on some line y = x + c , so now you can group all the points lying on a line based on c = y-x

Now process these points on a single line separately. Also note now you only need one coordinate ie x or y.

My solution: CodeChef: Practical coding for everyone

2 Likes
3

thanks @hetp111. I’ll try it.