ECOO '17 R3 P3 - Region Selection

View as PDF

Submit solution

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

Author:
Problem types

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 Specifications

The input will contain 10 test cases. Each case begins with an integer N which represents the number of schools competing (1 \le N \le 100). N lines follow, each containing two integers X and Y, representing the locations of a school (1 \le X, Y \le 1\,000). No two schools will be at the same location.

For 40\% of the cases, N, X, Y \le 40.

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 10.

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

Output Specifications

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

Sample Input

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 2 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


Comments

There are no comments at the moment.