Number of points lying inside a rectangle as well as a triangle | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getArea ( int x1 , int y1 , int x2 , int y2 , int x3 , int y3 ) { return abs ( ( x1 * ( y2 - y3 ) + x2 * ( y3 - y1 ) + x3 * ( y1 - y2 ) ) / 2 ) ; } int isInside ( vector < vector < int > > triangle , vector < int > point ) { vector < int > A = triangle [ 0 ] ; vector < int > B = triangle [ 1 ] ; vector < int > C = triangle [ 2 ] ; int x = point [ 0 ] ; int y = point [ 1 ] ; int ABC = getArea ( A [ 0 ] , A [ 1 ] , B [ 0 ] , B [ 1 ] , C [ 0 ] , C [ 1 ] ) ; int BPC = getArea ( x , y , B [ 0 ] , B [ 1 ] , C [ 0 ] , C [ 1 ] ) ; int APC = getArea ( A [ 0 ] , A [ 1 ] , x , y , C [ 0 ] , C [ 1 ] ) ; int APB = getArea ( A [ 0 ] , A [ 1 ] , B [ 0 ] , B [ 1 ] , x , y ) ; return ABC == ( APC + APB + BPC ) ; } void countPoints ( vector < vector < int > > rectangle , vector < vector < int > > triangle , vector < vector < int > > points ) { int n = rectangle . size ( ) ; vector < vector < int > > triangle1 ; for ( int i = 1 ; i < n ; i ++ ) triangle1 . push_back ( rectangle [ i ] ) ; vector < vector < int > > triangle2 ; for ( int i = 0 ; i < 3 ; i ++ ) triangle2 . push_back ( rectangle [ i ] ) ; vector < vector < int > > triangle3 ; for ( int i = 0 ; i < 2 ; i ++ ) triangle3 . push_back ( rectangle [ i ] ) ; triangle3 . push_back ( rectangle [ 3 ] ) ; vector < vector < int > > triangle4 ; for ( int i = n - 2 ; i < n ; i ++ ) triangle4 . push_back ( rectangle [ i ] ) ; triangle4 . push_back ( rectangle [ 0 ] ) ; int ans = 0 ; for ( auto 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 condTwo condThree condFour ) && condFive ) ans += 1 ; } cout << ans ; } int main ( ) { vector < vector < int > > rectangle = { { 6 , 5 } , { 2 , 2 } , { 2 , 1 } , { 5 , 5 } } ; vector < vector < int > > points = { { 1 , 1 } , { 6 , 1 } , { 6 , 6 } , { 1 , 6 } } ; vector < vector < int > > triangle = { { 4 , 4 } , { 0 , 4 } , { 0 , -2 } } ; countPoints ( points , triangle , rectangle ) ; return 0 ; }