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 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.
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.
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
200 10000 21815
Migrated from old NTUJ.
ACM-ICPC Asia-Amritapuri Site 2009
| No. | Testdata Range | Score |
|---|