Animals And Monsters

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
IBMD.E.Shaw

Problem statement

Ninja lives in the village and has animal husbandry which consists of various animals like cows, sheep, etc. Ninjas’ village also has animal-eating monsters which eat animals that are not present in the fence of the husbandry. You have given the points array ‘POINTS’ having ‘N’ vertices which denote the coordinates in the X-Y plane of the fence and the coordinates of the animal ‘X’ and ‘Y’. The width of the fence is very large so the points present on the fence are considered to be inside. Find if the given animal is safe from monsters or not.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the number vertices of the fence.

The next ‘N’ lines will denote the coordinates of the fence in the X-Y place.

The ‘N + 1’th line will denote the coordinates of the animal in the X-Y plane.
Output Format : 
For each test case, return a single integer ‘1’ if the animal is safe, else print ‘0’.

Print output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 2*10^3
-10^4 <= X, Y <= 10^4

Time Limit: 1 sec
Sample Input 1 :
1
4
0 0
0 1
1 0
1 1
2 0
Sample Output 1 :
0
Explanation For Sample Input 1 :
The fencing and animal in the X-Y plane will be :


As the animal is outside of the fence, so it is not safe.
Sample Input 2 :
1
3
0 0
5 0
5 5
3 3
Sample Output 2 :
1
Hint

Think of an approach using the intersection of line segments.

Approaches (1)
Line Intersection

The basic idea is to make a horizontal line to the right of each point by extending it. We count the number of times the animal line segment intersects with the fence line segment. If the intersection is an odd number of times then the point lies in the circle, else it lies outside the circle.
 

Special case: When the coordinates of the animal are colinear with line segments of the fences, we check whether that point lies on the segment or not. If it lies on the segment it is considered to be inside the fence

 

Here is the algorithm :
 

  1. For the convenience of handling coordinates, we create a class (say, ‘POINT’) having ‘X’ and ‘Y’ as their data members and having a constructor to initialize points of the fence and the animal.
  2. Base case
    • If ‘N’ < 3, return 0.
  3. Create endpoints (say, ‘A1’ and ‘A2’) for line segments of animals and initialize them with coordinates (‘X’, ‘Y’) and (10000, ‘Y’) respectively.
  4. Create a variable (say, ‘COUNT’) that will store the number of lines intersected and initialize it with 0.
  5. Run a loop from 0 to ‘N - 1’ (say, iterator ‘i’) that will traverse all the vertices.
    • Create endpoints (say, ‘F1’ and ‘F2’) for line segments of animals and initialize them with coordinates (‘POINTS[i][0]’, ‘POINTS[i][1]’) and (‘POINTS[(i + 1) % N][0]’, ‘POINTS[(i + 1) % N][1]’) respectively.
    • Check if points ‘F1’, ‘F2, ‘A1’, and ‘A2’ intersect using INTERSECT function.
      • Check if points ‘F1’, ‘A1’, and ‘F2’ are colinear using the ORIENTATION function.
        • Check if point ‘A1’ is present on the line segment formed by endpoints ‘F1’ and ‘F2’ using the onLine function and return the values returned by the function.
    • Increment  ‘COUNT’ by 1.
  6. Check if ‘COUNT’ is odd or not.

 

INTERSECT(‘F1’, ‘F2, ‘A1’,  ‘A2’) (Function to find the intersection of line segments.)

 

  1. Create variables (say, ‘O1’, ‘O2’, ‘O3’, and ‘O4’) and store the orientations of the points in all possible combinations. ( Ex: ‘F1’, ‘F2’, ‘A1’; ‘A1’, ‘F1’, ‘A2’)
  2. Check if ‘O1’ is not equal to ‘O2’ and ‘O3’ is not equal to ‘O4.  (Intersection case)
    • Return TRUE.
  3. Check if ‘O1’ is equal to 0 and ‘A1’ lies on the line segment formed by ‘F1’ and ‘F2’  (Case when ‘A1’ is colinear to ‘F1’ and ‘F2’,  check whether ‘A1’ lies on a line segment or not).
    • Return TRUE.
  4. Similarly, check for ‘O2’, ‘O3’, and ‘O4’.
  5. Finally, return FALSE.

 

ORIENTATION(‘P’, ‘Q’, ‘R’) (Function to find the orientation.)
 

  1. Create a variable (say, ‘VAL’) and find orientation using the formula, (‘Q.Y’ - ‘P.Y’) * (‘R.X’ - ‘Q.X’) - (‘Q.X’ - ‘P.X’) * (‘R.Y’ - ‘Q.Y’).
  2. Check if ‘VAL’ is equal to 0, return 0. (Colinear case)
  3. Check if ‘VAL’ is greater than 0, return 1.  (Counterwise case)
  4. Return 2.  (Counterclockwise case)
     

onLine(‘P’, ‘Q’, ‘R’) (Function to check whether a point lies on the line or not.)
 

  1. Check if ‘Q.X’ is smaller than equal to the maximum of ‘P.X’ and ‘R.X’ and greater than the minimum of ‘P.X’ and ‘R.X’ and similarly for ‘Q.Y’.
    • Return TRUE.
  2. Return FALSE.
Time Complexity

O(N), where ‘N’ is the number of vertices of the fence.
 

We traverse all the vertices of the fence to find the intersection. Therefore, the overall time complexity will be O(N).

Space Complexity

O(1)

 

We don’t use any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Animals And Monsters
Full screen
Console