ECOO '16 R1 P4 - Kayenne

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 10.0s
Memory limit: 64M

Problem type

The village of Kayenne is divided into a square grid. Residents build their houses where the grid lines intersect. The location of each house is described by a pair of X and Y coordinates, where (0, 0) is the point at the exact centre of town. Each grid line is exactly the same distance from the grid lines on either side of it. Kayenne stretches out from the centre for 200 grid lines North, East, South and West. Individuals or families who move to Kayenne are assigned a circular area in which to build their house. This area is centred on a particular grid point and has a radius of 50. The newcomers are allowed to build their houses on any empty grid point within that circular area (including on the circle boundary).

Some households in Kayenne are Democrat and others are Republican. New households don't get to choose their political affiliations. Instead, their three closest neighbours (determined by the straight line distance between grid locations) vote on their affiliation and the newcomers must abide by the majority decision. Of course, Democrat households always vote that newcomers should be Democrats, and Republican households always vote that they should be Republicans. Occasionally there are ties for the 3^{rd} closest neighbour. When this happens, all the neighbours who are the same distance as the 3^{rd} closest are also allowed to vote. This can result in an even number of votes, which means that the vote can be tied. In these cases, the newcomers will be Democrats.

The input will contain 10 test cases.

The first line of each test case will consist of two integers C_x and C_y, separated by a space, representing the coordinates of the centre of a newcomer's circular building area (-150 \le C_x, C_y \le 150).

The next 100 lines will each contain two integers H_x and H_y and an uppercase letter A separated by single spaces, representing the coordinates and political affiliation of the existing houses in Kayenne (-200 \le H_x, H_y \le 200, A \in [\texttt D, \texttt R]).

Your program must output a number representing the percentage chance (rounded to one decimal place) that a newcomer assigned to this circular building area will end up a Democratic household, assuming they choose their building site randomly from the available sites in their area.

Note that the sample data below contains only 1 test case with 20 houses but the test data will contain 10 test cases with 100 houses each.

Sample Input

-81 83
15 -198 R
-17 89 R
197 -174 R
-67 89 D
180 -101 D
-78 -173 R
182 121 D
-129 179 R
-100 -53 D
64 -61 D
-123 -152 D
-15 -67 R
20 194 D
125 16 D
133 -28 D
19 -9 R
121 168 D
165 -39 R
-170 -3 D
-27 61 D

Sample Output

88.7

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Stella Lau (University of Cambridge)
Greg Reid (St. Francis Xavier Secondary School, Mississauga)
Dino Baron (University of Waterloo)
John Ketelaars (ECOO-CS Communications)
David Stermole (ECOO-CS President)

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


Comments


  • -1
    Pokado  commented on March 29, 2017, 3:25 a.m.

    radius of 50 what? Do they mean 50 grid lines, or is the radius irrelevant to the solution.


    • 1
      kevin51jiang  commented on March 23, 2018, 4:04 a.m.

      @Pokado

      I'm pretty sure they mean that the area they are allowed to build the house at has a circular radius of 50, centered around the point they give you.

      You have to find the avg possibility of them being a democrat if they chose to build their house randomly inside that circle.