2001 Canadian Computing Competition, Stage 2
Day 2, Problem 2: Fast Food
You are planning to open a new Veggie Vittles fast-food restaurant franchise. N franchises are available, and you must determine the most desirable locations.
The city is a perfect square, 10 km 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.
InputThe input may contain several test cases. The first line of each test case contains N (1 ≤ N ≤ 50); the number of Veggie Vittles to be opened. N lines follow, each giving the x,y coordinates of each restaurant; each coordinate value is an integer between 0 and 10. The input ends with a 0 for the value of N.
OutputThe 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 (x,y) 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.
3 3 5 5 7 7 5 0
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.
Point Value: 15
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3