Dadas dos arrays 2D rectángulo[][] y triángulo[][] , que representan las coordenadas de los vértices de un rectángulo y un triángulo respectivamente, y otra array puntos[][] que consta de N coordenadas, la tarea es contar el número de puntos que se encuentran dentro del rectángulo y del triángulo.
Ejemplos:
Entrada: rectángulo[][] = {{1, 1}, {6, 1}, {6, 6}, {1, 6}}, triángulo[][] = {{4, 4}, {0, 4}, {0, -2}}, puntos[][] = {{6, 5}, {2, 2}, {2, 1}, {5, 5}}
Salida: 2
Explicación:
De la imagen de arriba, está claro que las coordenadas (2, 1) y (2, 2) se encuentran dentro del rectángulo y el triángulo dados.
Por lo tanto, la cuenta es 2.
Entrada: rectángulo[][] = {{-2, -2}, {2, -2}, {2, 2}, {-2, 2}}, triángulo[][] = {{0, 0} , {1, 1}, {-1, -1}}, puntos[][] = {{0, 2}, {-2, -2}, {2, -2}}
Salida: 2
Enfoque: El problema dado se puede resolver con base en la siguiente observación:
Cualquiera de los tres vértices de un rectángulo se puede conectar para formar un triángulo.
Por lo tanto, el número de triángulos posibles de un rectángulo dado es 4.
Por lo tanto, para resolver el problema, la idea es comprobar si el punto dado se encuentra dentro del triángulo dado y cualquiera de los cuatro triángulos que se obtienen del rectángulo o no. Siga los pasos a continuación para resolver el problema:
- Inicializa cuatro listas, por ejemplo , triangulo1, triangulo2, triangulo3 y triangulo4 , para almacenar las coordenadas de los vértices de los cuatro triángulos posibles de un rectángulo.
- Complete las listas inicializadas anteriores considerando tres vértices del rectángulo a la vez.
- Inicialice una variable, digamos ans como 0 , para almacenar el número de puntos que se encuentran dentro del triángulo y del rectángulo.
- Recorra la array puntos[][] y verifique si existe algún punto que se encuentre dentro de cualquiera de los cuatro triángulos obtenidos, así como dentro del triángulo dado o no. Si se encuentra que es cierto, entonces incremente ans en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans como el conteo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate area of a triangle
int getArea(int x1,int y1,int x2,int y2,int x3,int y3)
{
// Return the resultant area
return abs((x1 * (y2 - y3) +
x2 * (y3 - y1) +
x3 * (y1 - y2)) / 2);
}
// Function to check if a point
// lies inside a triangle or not
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];
// Calculate area of triangle ABC
int ABC = getArea(A[0], A[1],
B[0], B[1],
C[0], C[1]);
// Calculate area of triangle
// formed by connecting B, C, point
int BPC = getArea(x, y, B[0],
B[1], C[0],
C[1]);
// Calculate area of triangle
// formed by connecting A, C, point
int APC = getArea(A[0], A[1], x,
y, C[0], C[1]);
// Calculate area of triangle
// formed by connecting A, B, point
int APB = getArea(A[0], A[1], B[0],
B[1], x, y);
// Check if the sum of the areas of
// above three triangles the same as ABC
return ABC == (APC + APB + BPC);
}
// Function to count the number of points
// lying inside a triangle & rectangle
void countPoints(vector<vector<int>> rectangle,vector<vector<int>> triangle,vector<vector<int>> points){
// Stores the coordinates of the
// vertices of the triangles
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]);
// Stores the number of points lying
// inside the triangle and rectangle
int ans = 0;
// Traverse the array of points
for(auto point:points)
{
// Stores whether the current point
// lies inside triangle1 or not
int condOne = isInside(triangle1, point);
// Stores whether the current point
// lies inside triangle2 or not
int condTwo = isInside(triangle2, point);
// Stores whether the current point
// lies inside triangle3 or not
int condThree = isInside(triangle3, point);
// Stores whether the current point
// lies inside triangle4 or not
int condFour = isInside(triangle4, point);
// Stores whether the current point
// lies inside given triangle or not
int condFive = isInside(triangle, point);
// If current point lies inside
// given triangle as well as inside
// any of the four obtained triangles
if ((condOne || condTwo || condThree || condFour) && condFive)
ans += 1;
}
// Print the count of points
cout << ans;
}
// Driver Code
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;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to calculate area of a triangle
static int getArea(int x1, int y1, int x2,
int y2, int x3, int y3)
{
// Return the resultant area
return Math.abs((x1 * (y2 - y3) +
x2 * (y3 - y1) +
x3 * (y1 - y2)) / 2);
}
// Function to check if a point
// lies inside a triangle or not
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);
// Calculate area of triangle ABC
int ABC = getArea(A.get(0), A.get(1),
B.get(0), B.get(1),
C.get(0), C.get(1));
// Calculate area of triangle
// formed by connecting B, C, point
int BPC = getArea(x, y, B.get(0),
B.get(1), C.get(0),
C.get(1));
// Calculate area of triangle
// formed by connecting A, C, point
int APC = getArea(A.get(0), A.get(1), x,
y, C.get(0), C.get(1));
// Calculate area of triangle
// formed by connecting A, B, point
int APB = getArea(A.get(0), A.get(1), B.get(0),
B.get(1), x, y);
// Check if the sum of the areas of
// above three triangles the same as ABC
return ABC == (APC + APB + BPC) ? 1 :0;
}
// Function to count the number of points
// lying inside a triangle & rectangle
static void countPoints(ArrayList<ArrayList<Integer>> rectangle,
ArrayList<ArrayList<Integer>> triangle,
ArrayList<ArrayList<Integer>> points)
{
// Stores the coordinates of the
// vertices of the triangles
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));
// Stores the number of points lying
// inside the triangle and rectangle
int ans = 0;
// Traverse the array of points
for(ArrayList<Integer> point:points)
{
// Stores whether the current point
// lies inside triangle1 or not
int condOne = isInside(triangle1, point);
// Stores whether the current point
// lies inside triangle2 or not
int condTwo = isInside(triangle2, point);
// Stores whether the current point
// lies inside triangle3 or not
int condThree = isInside(triangle3, point);
// Stores whether the current point
// lies inside triangle4 or not
int condFour = isInside(triangle4, point);
// Stores whether the current point
// lies inside given triangle or not
int condFive = isInside(triangle, point);
// If current point lies inside
// given triangle as well as inside
// any of the four obtained triangles
if ((condOne != 0 || condTwo != 0 ||
condThree != 0 || condFour != 0) &&
condFive != 0)
ans += 1;
}
// Print the count of points
System.out.println(ans);
}
// Driver Code
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);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach # Function to calculate area of a triangle def getArea(x1, y1, x2, y2, x3, y3): # Return the resultant area return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2) # Function to check if a point # lies inside a triangle or not def isInside(triangle, point): A, B, C = triangle x, y = point # Calculate area of triangle ABC ABC = getArea(A[0], A[1], B[0], B[1], C[0], C[1]) # Calculate area of triangle # formed by connecting B, C, point BPC = getArea(x, y, B[0], B[1], C[0], C[1]) # Calculate area of triangle # formed by connecting A, C, point APC = getArea(A[0], A[1], x, y, C[0], C[1]) # Calculate area of triangle # formed by connecting A, B, point APB = getArea(A[0], A[1], B[0], B[1], x, y) # Check if the sum of the areas of # above three triangles the same as ABC return ABC == (APC + APB + BPC) # Function to count the number of points # lying inside a triangle & rectangle def countPoints(rectangle, triangle, points): # Stores the coordinates of the # vertices of the triangles triangle1 = rectangle[1:] triangle2 = rectangle[:3] triangle3 = rectangle[:2] triangle3.append(rectangle[3]) triangle4 = rectangle[-2:] triangle4.append(rectangle[0]) # Stores the number of points lying # inside the triangle and rectangle ans = 0 # Traverse the array of points for point in points: # Stores whether the current point # lies inside triangle1 or not condOne = isInside(triangle1, point) # Stores whether the current point # lies inside triangle2 or not condTwo = isInside(triangle2, point) # Stores whether the current point # lies inside triangle3 or not condThree = isInside(triangle3, point) # Stores whether the current point # lies inside triangle4 or not condFour = isInside(triangle4, point) # Stores whether the current point # lies inside given triangle or not condFive = isInside(triangle, point) # If current point lies inside # given triangle as well as inside # any of the four obtained triangles if (condOne or condTwo or condThree \ or condFour) and condFive: ans += 1 # Print the count of points print(ans) # Driver Code rectangle = [[6, 5], [2, 2], [2, 1], [5, 5]] points = [[1, 1], [6, 1], [6, 6], [1, 6]] triangle = [[4, 4], [0, 4], [0, -2]] countPoints(points, triangle, rectangle)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to calculate area of a triangle
static int getArea(int x1, int y1, int x2,
int y2, int x3, int y3)
{
// Return the resultant area
return Math.Abs((x1 * (y2 - y3) +
x2 * (y3 - y1) +
x3 * (y1 - y2)) / 2);
}
// Function to check if a point
// lies inside a triangle or not
static int isInside(List<List<int>> triangle,
List<int> point)
{
List<int> A = triangle[0];
List<int> B = triangle[1];
List<int> C = triangle[2];
int x = point[0];
int y = point[1];
// Calculate area of triangle ABC
int ABC = getArea(A[0], A[1],
B[0], B[1],
C[0], C[1]);
// Calculate area of triangle
// formed by connecting B, C, point
int BPC = getArea(x, y, B[0],
B[1], C[0],
C[1]);
// Calculate area of triangle
// formed by connecting A, C, point
int APC = getArea(A[0], A[1], x,
y, C[0], C[1]);
// Calculate area of triangle
// formed by connecting A, B, point
int APB = getArea(A[0], A[1], B[0],
B[1], x, y);
// Check if the sum of the areas of
// above three triangles the same as ABC
return ABC == (APC + APB + BPC) ? 1 :0;
}
// Function to count the number of points
// lying inside a triangle & rectangle
static void countPoints(List<List<int>> rectangle,
List<List<int>> triangle,
List<List<int>> points)
{
// Stores the coordinates of the
// vertices of the triangles
int n = rectangle.Count;
List<List<int>> triangle1 = new List<List<int>>();
for(int i = 1; i < n; i++)
triangle1.Add(rectangle[i]);
List<List<int>> triangle2 = new List<List<int>>();
for(int i = 0; i < 3; i++)
{
triangle2.Add(rectangle[i]);
}
List<List<int>> triangle3 = new List<List<int>>();
for(int i = 0; i < 2; i++)
{
triangle3.Add(rectangle[i]);
}
triangle3.Add(rectangle[3]);
List<List<int>> triangle4 = new List<List<int>>();
for(int i = n - 2; i < n; i++)
{
triangle4.Add(rectangle[i]);
}
triangle4.Add(rectangle[0]);
// Stores the number of points lying
// inside the triangle and rectangle
int ans = 0;
// Traverse the array of points
foreach(List<int> point in points)
{
// Stores whether the current point
// lies inside triangle1 or not
int condOne = isInside(triangle1, point);
// Stores whether the current point
// lies inside triangle2 or not
int condTwo = isInside(triangle2, point);
// Stores whether the current point
// lies inside triangle3 or not
int condThree = isInside(triangle3, point);
// Stores whether the current point
// lies inside triangle4 or not
int condFour = isInside(triangle4, point);
// Stores whether the current point
// lies inside given triangle or not
int condFive = isInside(triangle, point);
// If current point lies inside
// given triangle as well as inside
// any of the four obtained triangles
if ((condOne != 0 || condTwo != 0 ||
condThree != 0 || condFour != 0) &&
condFive != 0)
ans += 1;
}
// Print the count of points
Console.WriteLine(ans);
}
// Driver Code
static public void Main ()
{
List<List<int>> rectangle = new List<List<int>>();
List<List<int>> points = new List<List<int>>();
List<List<int>> triangle = new List<List<int>>();
rectangle.Add(new List<int>(){6, 5});
rectangle.Add(new List<int>(){2, 2});
rectangle.Add(new List<int>(){2, 1});
rectangle.Add(new List<int>(){5, 5});
points.Add(new List<int>(){1, 1});
points.Add(new List<int>(){6, 1});
points.Add(new List<int>(){6, 6});
points.Add(new List<int>(){1, 6});
triangle.Add(new List<int>(){4, 4});
triangle.Add(new List<int>(){0, 4});
triangle.Add(new List<int>(){0, -2});
countPoints(points, triangle, rectangle);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for the above approach
// Function to calculate area of a triangle
function getArea(x1,y1,x2,y2,x3,y3)
{
// Return the resultant area
return Math.abs((x1 * (y2 - y3) +
x2 * (y3 - y1) +
x3 * (y1 - y2)) / 2);
}
// Function to check if a point
// lies inside a triangle or not
function isInside(triangle,point)
{
let A = triangle[0];
let B = triangle[1];
let C = triangle[2];
let x = point[0];
let y = point[1];
// Calculate area of triangle ABC
let ABC = getArea(A[0], A[1],
B[0], B[1],
C[0], C[1]);
// Calculate area of triangle
// formed by connecting B, C, point
let BPC = getArea(x, y, B[0],
B[1], C[0],
C[1]);
// Calculate area of triangle
// formed by connecting A, C, point
let APC = getArea(A[0], A[1], x,
y, C[0], C[1]);
// Calculate area of triangle
// formed by connecting A, B, point
let APB = getArea(A[0], A[1], B[0],
B[1], x, y);
// Check if the sum of the areas of
// above three triangles the same as ABC
return ABC == (APC + APB + BPC) ? 1 :0;
}
// Function to count the number of points
// lying inside a triangle & rectangle
function countPoints(rectangle,triangle,points)
{
// Stores the coordinates of the
// vertices of the triangles
let n = rectangle.length;
let triangle1 = [];
for(let i = 1; i < n; i++)
triangle1.push(rectangle[i]);
let triangle2 = [];
for(let i = 0; i < 3; i++)
{
triangle2.push(rectangle[i]);
}
let triangle3 = [];
for(let i = 0; i < 2; i++)
{
triangle3.push(rectangle[i]);
}
triangle3.push(rectangle[3]);
let triangle4 = [];
for(let i = n - 2; i < n; i++)
{
triangle4.push(rectangle[i]);
}
triangle4.push(rectangle[0]);
// Stores the number of points lying
// inside the triangle and rectangle
let ans = 0;
// Traverse the array of points
for(let point=0;point<points.length;point++)
{
// Stores whether the current point
// lies inside triangle1 or not
let condOne = isInside(triangle1, points[point]);
// Stores whether the current point
// lies inside triangle2 or not
let condTwo = isInside(triangle2, points[point]);
// Stores whether the current point
// lies inside triangle3 or not
let condThree = isInside(triangle3, points[point]);
// Stores whether the current point
// lies inside triangle4 or not
let condFour = isInside(triangle4, points[point]);
// Stores whether the current point
// lies inside given triangle or not
let condFive = isInside(triangle, points[point]);
// If current point lies inside
// given triangle as well as inside
// any of the four obtained triangles
if ((condOne != 0 || condTwo != 0 ||
condThree != 0 || condFour != 0) &&
condFive != 0)
ans += 1;
}
// Print the count of points
document.write(ans+"<br>");
}
// Driver Code
let rectangle =[];
let points = [];
let triangle = [];
rectangle.push([6, 5]);
rectangle.push([2, 2]);
rectangle.push([2, 1]);
rectangle.push([5, 5]);
points.push([1, 1]);
points.push([6, 1]);
points.push([6, 6]);
points.push([1, 6]);
triangle.push([4, 4]);
triangle.push([0, 4]);
triangle.push([0, -2]);
countPoints(points, triangle, rectangle);
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA