Number of points lying inside a rectangle as well as a triangle | Java program for the above approach ; Function to calculate area of a triangle ; Return the resultant area ; Function to check if a point lies inside a triangle or not ; Calculate area of triangle ABC ; Calculate area of triangle formed by connecting B , C , point ; Calculate area of triangle formed by connecting A , C , point ; Calculate area of triangle formed by connecting A , B , point ; Check if the sum of the areas of above three triangles the same as ABC ; Function to count the number of points lying inside a triangle & rectangle ; Stores the coordinates of the vertices of the triangles ; Stores the number of points lying inside the triangle and rectangle ; Traverse the array of points ; Stores whether the current point lies inside triangle1 or not ; Stores whether the current point lies inside triangle2 or not ; Stores whether the current point lies inside triangle3 or not ; Stores whether the current point lies inside triangle4 or not ; Stores whether the current point lies inside given triangle or not ; If current point lies inside given triangle as well as inside any of the four obtained triangles ; Print the count of points ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static int getArea ( int x1 , int y1 , int x2 , int y2 , int x3 , int y3 ) { return Math . abs ( ( x1 * ( y2 - y3 ) + x2 * ( y3 - y1 ) + x3 * ( y1 - y2 ) ) / 2 ) ; } static int isInside ( ArrayList < ArrayList < Integer > > triangle , ArrayList < Integer > point ) { ArrayList < Integer > A = triangle . get ( 0 ) ; ArrayList < Integer > B = triangle . get ( 1 ) ; ArrayList < Integer > C = triangle . get ( 2 ) ; int x = point . get ( 0 ) ; int y = point . get ( 1 ) ; int ABC = getArea ( A . get ( 0 ) , A . get ( 1 ) , B . get ( 0 ) , B . get ( 1 ) , C . get ( 0 ) , C . get ( 1 ) ) ; int BPC = getArea ( x , y , B . get ( 0 ) , B . get ( 1 ) , C . get ( 0 ) , C . get ( 1 ) ) ; int APC = getArea ( A . get ( 0 ) , A . get ( 1 ) , x , y , C . get ( 0 ) , C . get ( 1 ) ) ; int APB = getArea ( A . get ( 0 ) , A . get ( 1 ) , B . get ( 0 ) , B . get ( 1 ) , x , y ) ; return ABC == ( APC + APB + BPC ) ? 1 : 0 ; } static void countPoints ( ArrayList < ArrayList < Integer > > rectangle , ArrayList < ArrayList < Integer > > triangle , ArrayList < ArrayList < Integer > > points ) { int n = rectangle . size ( ) ; ArrayList < ArrayList < Integer > > triangle1 = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = 1 ; i < n ; i ++ ) triangle1 . add ( rectangle . get ( i ) ) ; ArrayList < ArrayList < Integer > > triangle2 = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = 0 ; i < 3 ; i ++ ) { triangle2 . add ( rectangle . get ( i ) ) ; } ArrayList < ArrayList < Integer > > triangle3 = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = 0 ; i < 2 ; i ++ ) { triangle3 . add ( rectangle . get ( i ) ) ; } triangle3 . add ( rectangle . get ( 3 ) ) ; ArrayList < ArrayList < Integer > > triangle4 = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = n - 2 ; i < n ; i ++ ) { triangle4 . add ( rectangle . get ( i ) ) ; } triangle4 . add ( rectangle . get ( 0 ) ) ; int ans = 0 ; for ( ArrayList < Integer > point : points ) { int condOne = isInside ( triangle1 , point ) ; int condTwo = isInside ( triangle2 , point ) ; int condThree = isInside ( triangle3 , point ) ; int condFour = isInside ( triangle4 , point ) ; int condFive = isInside ( triangle , point ) ; if ( ( condOne != 0 condTwo != 0 condThree != 0 condFour != 0 ) && condFive != 0 ) ans += 1 ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { ArrayList < ArrayList < Integer > > rectangle = new ArrayList < ArrayList < Integer > > ( ) ; ArrayList < ArrayList < Integer > > points = new ArrayList < ArrayList < Integer > > ( ) ; ArrayList < ArrayList < Integer > > triangle = new ArrayList < ArrayList < Integer > > ( ) ; rectangle . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 5 ) ) ) ; rectangle . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 2 ) ) ) ; rectangle . add ( new ArrayList < Integer > ( Arrays . asList ( 2 , 1 ) ) ) ; rectangle . add ( new ArrayList < Integer > ( Arrays . asList ( 5 , 5 ) ) ) ; points . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 1 ) ) ) ; points . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 1 ) ) ) ; points . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 6 ) ) ) ; points . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 6 ) ) ) ; triangle . add ( new ArrayList < Integer > ( Arrays . asList ( 4 , 4 ) ) ) ; triangle . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , 4 ) ) ) ; triangle . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , - 2 ) ) ) ; countPoints ( points , triangle , rectangle ) ; } }