Connection Status:
Competition Arena > PlaneGame

PlaneGame

SRM 674 · 2015-11-03 · by FatalEagle

SRM 674 · 2015-11-03 · by FatalEagle · Simple Math
Class Name: PlaneGame
Return Type: int
Method Name: bestShot
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Jerry is playing a rather plain computer game. The game is played in the 2D Cartesian plane. At the beginning of the game there are some points in the plane. You are given their coordinates in the int[]s x and y. That is, for each valid i there is a point at (x[i], y[i]).

The objective of the game is to make a single shot that will eliminate as many of these points as possible. When Jerry takes the shot, it will eliminate all points that (at that moment) lie on the x-axis and also all points that lie on the y-axis.

Before Jerry takes the shot, he may perform a sequence of zero or more actions. Each action can be of either of the following two types:

  • He may translate all points by any vector (the same for all points). In other words, he may shift all points in the same direction by the same distance.
  • He may rotate all points around the origin by any angle (the same for all points).

Note that it is possible that after an action some points will have non-integer coordinates.

Find and return the maximum number of points Jerry can eliminate in one shot.

Constraints

  • x will contain between 1 and 50 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element of x and y will be between -1,000,000 and 1,000,000, inclusive.
  • No two points will have the same coordinates.
Examples
0)
{0, 5}
{0, 5}
Returns: 2

At the beginning of the game there are two points: one at (0, 0) and the other at (5, 5). Jerry can shift both points by 5 in the negative y direction. This will move the points to (0, -5) and (5, 0). Then Jerry can take the shot and eliminate both points. Therefore, the answer is 2.

1)
{0, -1, 1, 1, -1}
{0, -1, -1, 1, 1}
Returns: 5
2)
{0, 0, 0, 1, -1}
{0, 1, -1, 0, 0}
Returns: 5
3)
{0, -3, 3, 3, -3, 0, 0, 3, -3}
{0, -3, -3, 3, 3, 3, -3, 0, 0}
Returns: 5
4)
{0}
{0}
Returns: 1

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PlaneGame with a public method int bestShot(vector<int> x, vector<int> y) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous