Mock CCO '18 Contest 3 Problem 1 - Roger Meets For DMPG

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.18s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger is organizing the Don Mills Programming Gala! He has assembled N loyal assistants who will help him run this event.

Each of them lives in a house placed at some lattice point in the plane. Due to zoning requirements, no two houses can have Manhattan distance 1 from each other.

Roger wants everyone to meet up to discuss final logistics for the DMPG. He wishes to find an optimal lattice point for everyone to meet up, and he will do this by minimizing the sum of the Manhattan distances that everyone has to walk to attend the meetup. To respect the privacy of his assistants, he will not permit the meeting location to be someone's house.


2 \le N \le 10^4

-10^4 \le x_i, y_i \le 10^4

All (x_i, y_i) are distinct.

Input Specification

The first line will contain a single integer N.

Each of the next N lines will contain two integers, a lattice point (x_i, y_i) indicating that one of Roger's assistants lives at that location.

Output Specification

Output two space-separated integers. The first one is the minimum sum of Manhattan distances. The second one is the number of valid lattice points that attain this desired sum.

Sample Input

1 -3
0 1
-2 1
1 -1

Sample Output

10 4


There are no comments at the moment.