CCO '01 P5 - Fast Food

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 64M

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
Canadian Computing Competition: 2001 Stage 2, Day 2, Problem 2

You are planning to open a new Veggie Vittles fast-food restaurant franchise. franchises are available, and you must determine the most desirable locations.

The city is a perfect square, in linear dimension. The population density and demographics are uniform throughout the area of the city. You wish to choose your restaurant's location so that it is the Veggie Vittles that is the closest to the greatest possible fraction of the city's population.

Input Specification

The input may contain several test cases. The first line of each test case contains ; the number of Veggie Vittles to be opened. lines follow, each giving the coordinates of each restaurant; each coordinate value is an integer between and . The input ends with a 0 for the value of .

Output Specification

The output from your program consists of a list for the franchise locations. Print one line for each location, in the same order as the input, giving its coordinates followed by the percentage of the city's population for which it is the closest Veggie Vittles. Use the format given in the sample, rounding each percentage to the nearest integer. Do not worry about the details of rounding; any answer within 0.6 percentage points of the correct answer will be accepted. Output a blank line after each test case.

Sample Input

3
3 5
5 7
7 5
0

Sample Output

Restaurant at (3,5) serves 38% of the population.
Restaurant at (5,7) serves 25% of the population.
Restaurant at (7,5) serves 38% of the population.