Last Updated: 13 Dec, 2021

Points Visible

Hard

Asked in company

Solve now

Problem statement

You are standing at a point in the coordinate plane facing east. You are given an array of points ‘points’, you are also given an integer ‘angle’ i.e. your field of view and while standing on the given you are allowed to rotate but not move. Your task is to determine the maximum number of points visible to you simultaneously.

Suppose you rotate ‘d’ degrees counterclockwise.

PointDiagram

For Example:

You are given ‘location’ = [2, 2], ‘points’ = [[3,3], [4, 2], [3, 1]], ‘angle’ = 60. Due to the field of view only two, only 2, points [[2, 4], [3, 2]] simultaneously, are visible from the given position hence the answer is 2.

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains 2 space-separated integers, ‘N’, ‘angle’, where N represents the number of points in the given array and ‘angle’ is the given integer.

The second line of each test case contains two space-separated integers ‘x’ and ‘y’ representing coordinates of the location you are standing on.

The next ‘N’ lines of input contain two space-separated integers ‘a’ and ‘b’ representing ‘X’ and ‘Y’ coordinates of the points in the ‘points’ array.

Output Format:

For each test case, print a single integer representing the maximum number of points visible at a time.

Print a separate line in each test case.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
0 <= angle <= 360
0 <= x, y, a, b <= 1000

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, we will draw a line from where we are standing to each point and find the angle the line makes with the X-axis and store it in the array. Then we sort the array according to the angle.

To find the angle of point(Px, Py) from our standing coordinate(A, B) we use the formula:

tanθ = (Py - B) / (Px - A)

We can then start a sliding window of size ‘angle’ from the starting of the array. The maximum number of points in the sliding window will be the answer.

Here we will extend the sorted array with itself, with all the angles in the latter half will be increased by 2*π.

Algorithm:

Create an empty array sortedAngles
Set sameLocation as 0
Iterate point through points
- If point.x is equal to location.x and point.y is equal to location.y, Increase sameLocation by 1 and continue the loop
- Set pointAngle as tan inverse of (point.y - location.y) / (point.x - location.x)
- Insert pointAngle in sortedAngles
Sort the sortedAngles array
Add 2*π to all the values in sortedAngles and insert them back in the sortedAngles array
Set left and solution as 0
Iterate right from 0 to length of sortedAngles - 1
- While sortedAngles[right] - sortedAngles[left] less than angle*pi / 180
  - Increase left by 1
- Set solution as the maximum of itself and (right - left + 1)
Return solution + sameLocation

Solve now