Parking Ships#3131
Life on the great oceans has been good for Captain Blackbeard and his fellow pirates. They have gathered so many treasures that each of them is able to buy a house on their favorite island. The houses on this island are all placed in a long row along the beach line. Besides the house, every pirate is also able to buy his own ship to do some plundering. However, this introduces a new kind of problem.
Along the beach line, there is a long pier where every pirate can park his ship. Although there is enough space along the pier for all the ships, not every pirate will be able to park in front of his house. A pirate is happy with his parking space if some part of the parking space is in front of the center of his house. Captain Blackbeard has been given the difficult task of assigning the parking spaces to the pirates. A parking space for pirate is a range [a_i, b_i] (a_i, b_i \in \mathbb{R}) along the pier such that l_i \leq b_i - a_i, where l_i is the length of the ship of pirate . Thus, pirate is happy if a_i \leq x_i \leq b_i, where x_i is the center of the house of pirate . Clearly, parking spaces of different pirates must be interior disjoint (the ends of the ranges may coincide).
Above all, the captain wants a good parking space for himself, so he reserves his parking so that the center of his ship is aligned with the center of his house. He also wants to make as many pirates happy as possible. Can you help him?
The first line contains a single integer: the number of test cases. Each test case has the following format:
One line with one integer (1 \leq n \leq 1\,000): the number of pirates including the captain.
lines, each with two integers x_i (-10^9 \leq x_i \leq 10^9) and l_i (1 \leq l_i \leq 10^9): the center of the house of the -th pirate and the total length of his ship, respectively. The first pirate in the input is always the captain. It is guaranteed that all x_i are distinct.
For every test case, output a single integer on a separate line: the maximum number of happy pirates using an optimal assignment of the parking spaces. This number includes the captain. You may assume that space along the pier is unbounded in both directions.
Primer 1