Sucho and his Students
Sucho and his students went out to the field to play football. During the match, an ice cream guy arrives. Now Sucho wants his students to form a line to avoid chaos. But being a caring teacher, he wants his students to form the line with the least possible moves.
All his students are scattered around the field and their position is given by a pair (x, y) of integer coordinates. Students can move- in one move, one student can go 1 unit up, down, left or right(hence, he can change his x or his y co-ordinate by 1 or -1 in one move).
The students want to get into a horizontal line next to each other (so that their final positions are (x, y), (x+1, y), …, (x+N-1, y), for some x and y). Integers x and y, as well as the final order of soldiers along the horizontal line is arbitrary.
Two or more students can never occupy the same position at the same time.
Sucho is busy managing his students. Can you help him determine the minimum total number of moves of all the students that takes them into such configuration?/p>
The first line contains N, the total number of students present on the field.
The next N lines contain the initial position of each student. For each i, 1 ≤ i ≤ N, the (i+1)th line contains a pair of integers x[i] & y[i] separated by a single space, representing the coordinates of the ith student.
The output should contain one number which is the minimum total number of moves that the students makes to get into a horizontal line next to each other.
- 0≤ N ≤10^5
- -10000 ≤ x[i], y[i] ≤ 10000
3 1 0 2 4 3 2Output:
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.