Determine Locations with the Maximum Available Bandwidth in Java
Total points: 5 (this lab is optional; completing it will give you extra credits)
This project needs to be completed using Java and is an individual project. Naming of your programs must strictly follow the following convention: (1) one file for each part; (2) Lab3 followed by your Uid and I for part I (for example Lab3U00998499I.java). Upload only your source code (one file for each part) to the Pilot dropbox.
Your report must adequately describe your solutions, such as algorithm, pseudo code, implementation, time complexity etc.
The solution time complexity for this lab is an important consideration in grading. Therefore, you should use proper data structure and implement your solutions carefully. Test cases will exercise your programs thoroughly. Your programs should efficiently handle potentially large problems. Expect that your program produces results for all test cases within 4-5 seconds.
Grading: report (20%) and test cases passed (80%).
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
EXPLANATION:
In the figure below, streets are arranged as 2-D coordinates. Notice that the five coffee shops/intersections marked with a dark circle have total (and the maximum) bitrates of 12.
Get plagiarism Free Solution with complete Code in Java.
Please txt at WhatsApp or call for best Price:
+91 - 995 314 1035
Solution Includes: AI writing Detection and Plagiarism report with 100% Accuracy.