Complete Solution with Java Code and pseudo code.
Part I. Determine Locations with the Maximum Available Bandwidth
Alice lives in a city where there are a lot of coffee shops with Wi-Fi. In the city, there is
one coffee shop at every intersection of streets. Specifically, the city has M
(1<=M<=30,000) streets that run east and west, and N (1<=N<=1,000) streets that run
north and south. The distance between consecutive parallel streets is 1 meter (it is a
very compact city).
It also turns out that inside K (1<=K<=1,000) of the coffee shops, there is a wireless
network access point. Each wireless network access point will have a particular bitrate
and can reach R (1<=R<=30,000) meters from the coffee shop. In other words, a
wireless network access point from one coffee shop forms a circle with radius R
centered at that particular coffee shop. Moreover, if someone is at distance R, the
wireless network would be available, but if someone is at a distance larger than R,
he/she cannot access that wireless access point.
You can assume that each coffee shop has at most one wireless network access point,
but that multiple wireless networks may be available while sitting in that one coffee shop,
due to the proximity of other wireless network access points. Alice has a special device
in her computer that can use all of the available bitrates of as many wireless networks
as she can connect to. Alice would like to find out the maximum bitrate she can obtain,
and how many coffee shops would have that maximum capacity.
INPUT FORMAT:
Unlike previous labs, this lab reads input from the standard input. DO NOT include any
package statement in your program.
On the first line of input, you will be given the integer M, the number of east-west streets.
On the second line of input, you will be given the integer N, the number of north-south
streets. On the third line of input, you will be given the integer K, the number of coffee
shops with a wireless network.
On the next K lines, you will have 4 integers per line. The first integer, x, on each line
represents the north-south street on which the coffee shop is located, where 1 <=x<=N.
The second integer, y, on each line represents the east-west street on which the coffee
shop is located, where 1<=y<=M. The third integer, R, on each line represents the
radius of the wireless network from this particular coffee shop. The fourth integer, B , on
each line represents the bitrate of the wireless network from this particular coffee shop.
OUTPUT FORMAT:
Unlike previous labs, the output is to the standard output.
The output will be two lines long. The first line of output will be the integer representing
the maximum bitrate that can be obtained over all coffee shops. The second line of
output will be the number of coffee shops where this maximum bitrate can be obtained
SAMPLE INPUT:
3
5
3
1 3 2 5
3 1 2 7
5 1 1 5
SAMPLE OUTPUT:
12
5