[UVa] 13278 - Angry Birds Transformers

題目

Link: UVa 13278 - Angry Birds Transformers

13278 Angry Birds Transformers

Angry Birds Transformers is a side-scrolling shoot ’em up video game, the tenth installment in the Angry Birds series, a crossover between Angry Birds and Transformers, featuring battles between the Autobirds and Deceptihogs, Angry Birds versions of the Autobots and Decepticons. It is published by Rovio Entertainment with collaboration from Hasbro. [From Wikipedia] Six consecutive screenshots from this game are shown below:

13278_1

As you can see that as the player moves from left to right he can see new objects and can try to destroy them. Given the location of all the objects you will have to find out the maximum number of objects that are visible at any point of the game by the player. For simplicity you can assume the following things:

  1. All objects can be considered as points in a two dimensional Cartesian coordinate system.
  2. The player runs along the x axis from left to right.
  3. The viewing angle of the eye of the player is 90 degree and symmetric along the straight line \(x = p_x\) , where \(p_x\) is the abscissa of the player location.

The following image will make things clear:

13278_2

The goal is to find the maximum number of objects that can be seen at a time if the player moves along the x-axis. You can assume that if two or more objects and the location of the player are collinear, the player can still see all the objects. There is no need to find the location from where the maximum number of objects are visible as there can be more than one such place. The image above corresponds to the sample input.

Input

Input file contains at most 100 sets of inputs. Each set starts with a positive integer N ( \(N ≤ 10000\) ) denoting the total number of objects present in the scenario. Each of the next N lines contains two integers \((x_i, y_i)\) , denoting the Cartesian coordinate of the i-th object. Here ( \(0 < x_i ≤ 10000\) and \(0 < y_i ≤ 500\) ). Input is terminated by a line containing a single zero.

Output

For each set of inputs, produce one line of output. This line contains an integer that denotes the maximum number of objects visible by a player while running along the x-axis.

Sample Input

5
2 3
6 6
9 9
11 6
14 4
0

Sample Output

4

Hint

換成一維來處理

Code

C++

#include <iostream>

int main()
{
  constexpr const int BASE = 501;
  constexpr const int MAX = 10001 + 501 + BASE;

  int objects, x, y, view, result;
  int i;
  int *diagonal_left, *diagonal_right;

  std::ios::sync_with_stdio(false);

  while (std::cin >> objects && objects)
  {
    diagonal_left = new int[MAX]();
    diagonal_right = new int[MAX]();

    while (objects--)
    {
      std::cin >> x >> y;

      ++diagonal_left[BASE + x + y];
      ++diagonal_right[BASE + x - y];
    }

    view = 0, result = 0;
    for (i = 0; i <= MAX; ++i)
    {
      view += diagonal_right[i];
      if (view > result) result = view;
      view -= diagonal_left[i];
    }

    std::cout << result << std::endl;

    delete[] diagonal_left, diagonal_right;
  }
  return 0;
}

Show Comments