## ECOO '17 R3 P3 - Region Selection

View as PDF

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 256M

Author:
Problem types
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

The semi-final of the OCEE provincial competition happens at two different locations in Ontario. Ontario is a big place, so the locations need to be carefully chosen to accommodate the participants as best as possible.

In particular, a school's travel cost to the competition is equal to the square of the distance between the school and the nearest semi-final location. An optimal location selection would minimize the sum of these squared distances for every school.

Given the locations of all participating schools, can you determine the optimal placements of the two semi-finals?

#### Input Specification

The input will contain test cases. Each case begins with an integer which represents the number of schools competing . lines follow, each containing two integers and , representing the locations of a school . No two schools will be at the same location.

For of the cases, .

Note: Half of the marks per test case will be awarded if the difference between the program output and official answer is positive and at most .

Note: If one or more answers are not rounded to the nearest integer, marks will be deducted once.

#### Output Specification

For each test case, output the minimum total sum of every school's travel costs, rounded to the nearest integer.

3
1 1
2 2
3 3
6
1 1
2 1
3 1
1 4
2 4
3 4

#### Sample Output

1
4

Note: Only cases are shown in this sample.

#### ECOO 2017 Question Development Team

Kevin Forest ............................................... Sheridan College
John Ketelaars ....................................... ECOO-CS Communications
Stella Lau .......................................... University of Cambridge
Greg Reid .................. St. Francis Xavier Secondary School, Mississauga
Sam Scott .................................................... Mohawk College
Andrew Seidel ..................... John Fraser Secondary School, Mississauga
David Stermole ............................................ ECOO-CS President
Reyno Tilikaynen ..................................... University of Waterloo

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org