WIRELESS  Wireless
Bob is sitting at home with his computer. He would like to experience more social interaction, so he is planning a trip to a coffee shop with his computer.
Bob has lots of data about wireless networks and coffee shops in the city. In Bob’s city, there is one coffee shop at every intersection of streets. Specifically, Bob happens to live in a city with M streets (1 ≤ M ≤ 30000) that run east and west, and N streets (1 ≤ N ≤ 1000) that run north and south. As an added benefit, the distance between consecutive parallel streets is 1 metre (it is a very compact city).
It also turns out that inside K (1 ≤ K ≤ 1000) of the coffee shops, there is a wireless network station. Each wireless network station will have a particular bitrate B (1 ≤ B ≤ 1000) and can reach R metres (1 ≤ R ≤ 30000) from the coffee shop. In other words, a wireless network station 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, they cannot access that wireless point.
You can assume that each coffee shop has at most one wireless network stationed in it, but that multiple wireless networks may be available while sitting in that one coffee shop, due to the proximity of other wireless network stations.
Bob has a special device in his computer that can use all of the available bitrates of as many wireless networks as he can connect to.
Bob would like to find out the maximum bitrate he can obtain, and how many coffee shops would have that maximum capacity.
Input
On the first line of input, you will be given the integer M, the number of eastwest streets. On the second line of input, you will be given the integer N, the number of northsouth 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 northsouth street on which the coffee shop is located, where 1 ≤ x ≤ N. The second integer, y, on each line represents the eastwest 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
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
Explanation:
In the figure below, notice that the five coffee shops/intersections marked with a dark circle have total bitrates of 12.
hide comments
xashru:
20151002 00:26:02
Why do you use input data with invalid constraints? Your max bit rate is 1000*1000=1000000 which fits in 32 bit, but my code only gets accepted when I use 64 bit integer. Wasted lot of time. 

Naman:
20120726 10:52:22
My algorithm O(K*M*N) giving TLE even :


Brian Bi:
20091213 18:51:59
O(RC + K min(R,C)) 

P@inKill3R:
20091213 18:51:59
What is the time complexity of the optimal solution? My algorithm of O(K*R*R) is giving TLE!

Added by:  Brian Bi 
Date:  20090803 
Time limit:  0.234s1.171s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  2009 Canadian Computing Competition Stage 1  Question S5 