4. Kayenne

What is the Problem?

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 center of town. Each grid line is exactly the same distance from the grid lines on either side of it. Kayenne stretches out from the center for 200 grid lines North, South, East and West. Individuals or families who move to Kayenne are assigned a circular area in which to build their house. This area is centered 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 3rd closest neighbour. When this happens, all the neighbours who are the same distance as the 3rd 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.

DATA41.txt (DATA42.txt for the second try) will contain 10 test cases. The first line of each test case will consist of two integers 𝐶𝐶𝑥𝑥 and 𝐶𝐶𝑦𝑦, separated by a space, representing the coordinates of the center of a newcomer’s circular building area (−150 ≤ 𝐶𝐶𝑥𝑥,𝐶𝐶𝑦𝑦 ≤ 150). The next 100 lines will each contain two integers 𝐻𝐻𝑥𝑥 and 𝐻𝐻𝑦𝑦 and an uppercase letter 𝐴𝐴, separated by a space, representing the coordinates and political affiliation of the existing houses in Kayenne (−200≤𝐻𝐻𝑥𝑥,𝐻𝐻𝑦𝑦≤200,𝐴𝐴= “𝐷𝐷” 𝑜𝑜𝑜𝑜 “𝑅𝑅”). 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