ACM-ICPC Asia-Amritapuri Site 2009
Time Limit :: 8 Seconds
My brother and I love pizza. My brother ordered a pizza today with a number of toppings. Some of those toppings I love, like mushrooms, while there are some others that I hate, like olives. Even among the toppings I like (or the ones that I don't like), I like some more than the other, depending on the amount. Now my brother will let me take a wedge of any size from the pizza. This means I am allowed to make two cuts from the center of the pizza to its circumference, and can keep one of the two resulting pieces. If either cut goes through a topping, the entire topping belongs to that piece which contains the centre of the topping. I am not allowed to cut exactly through the centre of a topping. Each topping will thus remain entirely on one of the pieces. I would like to cut and choose the best piece possible for myself. Input Format: Input contains multiple test-cases. The first line of the input contains T, the number of test cases, followed by T testcases. The first line of each test case contains one integer N, the number of toppings. It is followed by N lines containing three space-separated integers each. Each line described a single topping. The first integer denotes my preference for the topping. The next two integers denote respectively the x and y co-ordinates of the centre of the topping. Input Constraints: 1 ≤ T ≤ 25 1 ≤ N ≤ 105 -105 ≤ preference ≤ 105 The point (x,y) will lie within the pizza, which is assumed to be a circle centered at (0, 0) with a radius of 109. The point will not be the centre itself. Multiple toppings may be centred at the same point. A set of test cases will not exceed 4MB in file size. Output Format: Output a single line per test-case, indicating the sum of the preferences of all the toppings on the best piece. The best piece is the one that has the maximum sum possible. Sample Input: 3 2 -100 28335 972 200 16646 1307 3 7265 341 160 -1000 17646 24060 2735 26741 7225 4 -8609 7286 1522 9243 30219 184 7255 19082 16933 5317 6845 0 Sample Output: 200 10000 21815 |