[Solution] Watering Well - Chapter 1 Meta Hacker Cup Solution
Note: The only difference between this chapter and chapter 2 is that here, coordinates are only up to .
Boss Rob just planted happy little trees in his yard, which can be represented on a Cartesian plane. The th tree is located at coordinates . Now, he's looking for the best spot to build a well in order to provide water to them. He considers the inconvenience of a potential well location to be the sum of the squared Euclidean distances to every tree:
Rob wants to pick a location for his well, well... well. Help him determine the inconvenience for different potential well locations, . To reduce output size, please print the sum of inconveniences for all potential well locations, modulo .
Constraints
All are distinct within a given test case.
All are distinct within a given test case.
The total sum of and across all test cases is at most .
Input Format
Input begins with a single integer , the number of test cases. For each case, there is first a line containing a single integer . Then, lines follow, the th of which contains two space-separated integers and . Then there is a line containing a single integer . Then, lines follow, the th of which contains two space-separated integers and .
Output Format
For the th test case, print a line containing "Case #i: ", followed by a single integer, the sum of inconveniences for all well locations, modulo .
Sample Explanation
The first two sample cases are depicted below:
![](https://scontent.fbho4-1.fna.fbcdn.net/v/t39.32972-6/302066777_3159344297659570_4546639623471702694_n.jpg?_nc_cat=108&ccb=1-7&_nc_sid=771dbb&_nc_ohc=_OlO-oic49UAX-6o_Dm&_nc_oc=AQnljsQH18cK3VrsN5w9irbpFSrY4-GK9nbrNToAOSU1EDLg1eCEsykwConMy_DuA403cxJ3xdc5GKb53uXg_jEV&_nc_ht=scontent.fbho4-1.fna&oh=00_AT98QwHWbfmspG9fTZ5Mnh236zFpdflqvLY4_gnMw76NJw&oe=6321F511)
In the first case, the total inconvenience is :
- For the well at , the inconvenience is the sum of the squared Euclidean distance to both trees, which is .
- For the well at , the inconvenience is .
In the second case, the total inconvenience is :
- For the well at , the inconvenience is .
- For the well at , the inconvenience is .
- For the well at , the inconvenience is .
No comments:
Post a Comment