SRM 621, D1, 275-Pointer (RadioRange)

James S. Plank

Web Sep 9 13:14:21 EDT 2015

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh
answers.txt
gen_input.cpp
Problem Given in Topcoder: January, 2014
Competitors who opened the problem: 765
Competitors who submitted a solution: 687
Number of correct solutions: 509
Accuracy (percentage correct vs those who opened): 66.5%
Average Correct Time: 25 minutes, 13 seconds.

For each city, you can come up with two distances, close and far, such that all radii less than close are good, and all radii greater than far are good. All radii between close and far are bad.

Think about how you would calculate close and far for each city. There are two cases -- when the city contains the radio tower, and when it doesn't. Draw a picture to visualize it -- for example, here is a drawing where the city contains the radio tower:

Can you see what close is? Can you calculate far as a function of x, y and r? Now, here is a drawing where the city does not contain the radio tower:

Can you calculate close and far as functions of x, y and r?

Make that your first step.

Now, your second step is to figure out what to do with these values of close and far.

Here's my hint. You are going to insert them into map keyed on doubles, with integers as values. When you insert a close value, you are going to subtract one from the value there (having values start at zero). When you insert a far value, you are going to add one to the value. To sentinelize, decrement the value in the map at Z by one.

Now, you run through the map, and use the keys and values to determine the segments of distance from the origin that are "good". Sum of all of these distances and divide by Z.

To help illustrate, suppose you have four cities, whose (x,y,r) values are as follows:

City 0: (10,0,5)
City 1: (-12,0,5)
City 2: (0,2,1)
City 3: (0,-18,1)

And suppose that Z equals 40.

Here are the close/far values:

City	Close	Far
0	5	15
1	7	17
2	1	3
3	17	19

And here is the map:

[1,-1], [3,1], [5,-1], [7,-1], [15,1], [17,0], [19,1], [40,-1].

Running through this map, you can identify that the "good" segments are [0-1],[3-5],[19-40]. Therefore, your answer is (1+2+21)/40 = 0.6.

Here's a picture of the cities and how you keep track of the regions of bad cities. I'm hoping this helps you figure out the map and what you do (if you click on it, you'll see it in full resolution):

If you want some help, here is the output of my program on the 7 given examples, and on an 8th, which is part of the topcoder test suite:

UNIX> a.out 0
Parameters:

X:       0
Y:       0
R:       5
Z:      10

My Map:

Key   0.000000  Val  1    Total:   0.000000
Key   5.000000  Val -1    Total:   0.000000
Key  10.000000  Val  1    Total:   5.000000
Answer: 0.50000000000000000000
0.5
UNIX> a.out 1
Parameters:

X:       0
Y:       0
R:      10
Z:      10

My Map:

Key   0.000000  Val  1    Total:   0.000000
Key  10.000000  Val  0    Total:   0.000000
Answer: 0.00000000000000000000
0
UNIX> a.out 2
Parameters:

X:      10
Y:      10
R:      10
Z:      10

My Map:

Key   0.000000  Val  0    Total:   0.000000
Key   4.142136  Val  1    Total:   4.142136
Key  10.000000  Val  1    Total:   4.142136
Key  24.142136  Val -1    Total:   4.142136
Answer: 0.41421356237309508996
0.414214
UNIX> a.out 3
Parameters:

X:      11     -11       0       0
Y:       0       0      11     -11
R:      10      10      10      10
Z:      31

My Map:

Key   0.000000  Val  0    Total:   0.000000
Key   1.000000  Val  4    Total:   1.000000
Key  21.000000  Val -4    Total:   1.000000
Key  31.000000  Val  1    Total:  11.000000
Answer: 0.35483870967741937275
0.354839
UNIX> a.out 4
Parameters:

X:     100
Y:     100
R:       1
Z:      10

My Map:

Key   0.000000  Val  0    Total:   0.000000
Key  10.000000  Val  1    Total:  10.000000
Key 140.421356  Val  1    Total:  10.000000
Key 142.421356  Val -1    Total:  10.000000
Answer: 1.00000000000000000000
1
UNIX> a.out 5
Parameters:

X:1000000000
Y:1000000000
R:1000000000
Z:1000000000

My Map:

Key   0.000000  Val  0    Total:   0.000000
Key 414213562.373095  Val  1    Total: 414213562.373095
Key 1000000000.000000  Val  1    Total: 414213562.373095
Key 2414213562.373095  Val -1    Total: 414213562.373095
Answer: 0.41421356237309503445
0.414214
UNIX> a.out 6
Parameters:

X:      20     -20       0       0
Y:       0       0      20     -20
R:      50      50      50      50
Z:     100

My Map:

Key   0.000000  Val  4    Total:   0.000000
Key  70.000000  Val -4    Total:   0.000000
Key 100.000000  Val  1    Total:  30.000000
Answer: 0.29999999999999998890
0.3
UNIX> a.out 7
Parameters:

X:       0     -60     -62     -60      63     -97
Y:     -72      67      61      -8     -32      89
R:       6       7       8       7       5       6
Z:     918

My Map:

Key   0.000000  Val  0    Total:   0.000000
Key  53.530984  Val  1    Total:  53.530984
Key  65.661163  Val  1    Total:  53.530984
Key  66.000000  Val  1    Total:  53.530984
Key  67.530984  Val -1    Total:  53.530984
Key  75.661163  Val -1    Total:  53.530984
Key  78.000000  Val -1    Total:  53.530984
Key  78.977008  Val  1    Total:  54.507992
Key  82.938868  Val  1    Total:  54.507992
Key  94.977008  Val -1    Total:  54.507992
Key  96.938868  Val -1    Total:  54.507992
Key 125.643458  Val  1    Total:  83.212582
Key 137.643458  Val -1    Total:  83.212582
Key 918.000000  Val  1    Total: 863.569124
Answer: 0.94070710689624714718
0.940707
UNIX> a.out 8
Parameters:

X:     -30     -56      11      13     -16
Y:      84      44      61     -72     -45
R:       2      10       4       5      10
Z:     423

My Map:

Key   0.000000  Val  0    Total:   0.000000
Key  37.759816  Val  1    Total:  37.759816
Key  57.759816  Val -1    Total:  37.759816
Key  57.983869  Val  1    Total:  37.983869
Key  61.217975  Val  1    Total:  37.983869
Key  65.983869  Val -1    Total:  37.983869
Key  68.164199  Val  1    Total:  37.983869
Key  78.164199  Val -1    Total:  37.983869
Key  81.217975  Val -1    Total:  37.983869
Key  87.196412  Val  1    Total:  43.962306
Key  91.196412  Val -1    Total:  43.962306
Key 423.000000  Val  1    Total: 375.765894
Answer: 0.88833544588696811140
0.888335
UNIX>