The Cthulhu Equation P73639


Statement
 

pdf   zip

html
Ph’nglui mglw’nafh Cthulhu R’lyeh wgah’nagl fhtagn.
The manuscripts of George Gammell Angell, Professor Emeritus of Semitic Languages in Brown University, Providence, Rhode Island, contain an extremely detailed recollection of reports of strange dreams suffered by artists, poets, and other people of a sensitive nature on the period between March 23rd and April 2nd, 1925, coinciding with the most considerable earthquake felt in New England for some years. He also noted how people like businesspeople or even scientists [sic] did not experience any disturbance to their usual sleep during the same period of time.

After he had determined the position of the city of R’lyeh based on the accounts of the late Gustaf Johansen, second mate of the two-masted schooner Emma of Auckland, New Zealand, and using the locations of the aforementioned events of disturbed dreaming, the Professor—who, unbeknownst to most, had also minored in Physics—was able to establish that the intensity of the Great Old Field G at a point follows an inverse-square law:

G = A · 
g
r2
  ,

where g is the greatness of the emitting Great Old One, r is the distance between It and the point, and A is what later became known as Angell’s constant. Professor Angell also estimated Cthulhu’s greatness to be exactly g = 1.91123 · 1010, and the value of the constant that now bears his name as A = 4.15287 m2.

Given the tolerance of the different people on Professor Angell’s map to the intensity G of the Great Old Field, can you compute for how many people that value will be exceeded, and thus they will enter a trance because of Cthulhu’s awakening in the city of R’lyeh?

Input

Input consists of several cases. Each case begins with the dimensions of the map H and W, its scale S (a positive real number), as well as the number of people P. Follow H lines with W characters each: ‘.’ for sea, ‘#’ for land, one ‘R’ for R’lyeh, and one ‘P’ for each person. Follow P tolerance values ti (positive real numbers) for each person, listed in north-to-south then west-to-east order. Input is terminated with a line with H = W = S = P = 0. Assume that both H and W are between 1 and 1000.

Each character represents a square cell S meters wide. The Earth is flat, despite anything you may have heard before, so you must use the usual Euclidean distance on the plane. Consider all people and Cthulhu as points located at the center of their cells.

Output

For every case, print the number of people that will enter a trance. The input cases will have no precision issues.

Public test cases
  • Input

    2 3 15000.0 2
    .RP
    P..
    100.0 200.0
    
    3 7 50000.0 4
    P#...#P
    #..R..#
    P#...#P
    1.5 2.5 3.5 4.5
    
    5 20 10000.0 7
    ##.P#..P..##..#..###
    ..###....#P####P###.
    ...P#.....#######...
    R...##..P###..#.....
    ....#.....#.....#P#.
    15.1 12.8 21.3 31.3 11.9 1.2 15.1
    
    0 0 0 0
    

    Output

    1
    2
    4
    
  • Information
    Author
    Edgar Gonzalez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setzè Concurs de Programació de la UPC - Final
    Date
    2018-09-19