Dados cuatro puntos (x, y) en la coordenada cartesiana. Encuentre el número posible de cuadriláteros que se pueden formar uniendo los cuatro puntos.
Ejemplos:
Input: A=(0, 9), B=(-1, 0), C=(5, -1), D=(5, 9) Output: Only one quadrilateral is possible (ABCD) in any orientation Input: A=(0, 9), B=(-1, 0), C=(5, -1), D=(0, 3) Output: 3 quadrilaterals are possible (ABCD), (ADBC), (ABDC)
Figura para el segundo ejemplo:
Acercarse:
- Necesitamos verificar si alguno de los puntos dados es el mismo. En caso afirmativo, no de cuadrilátero = 0
- Luego, debemos verificar si alguno de los 3 puntos de los 4 puntos dados es colineal o no. En caso afirmativo, no de cuadrilátero = 0. Verifique el programa para verificar si tres puntos son enlaces colineales para verificar la colinealidad de 3 puntos.
-
- si es un cuadrilátero convexo entonces solo hay un cuadrilátero posible .
- si es un cuadrilátero cóncavo entonces hay 3 cuadriláteros posibles .
Esto se puede determinar mediante ¿Cómo verificar si dos segmentos de línea dados se cruzan? de diagonales
En el caso de un cuadrilátero convexo , las diagonales se intersecarán, mientras que en el caso de un cuadrilátero cóncavo, las diagonales no se intersecarán.
Como no conocemos la orientación de los puntos, no podemos determinar específicamente las diagonales, por lo que todos los segmentos de línea distintos (sin puntos comunes en los dos segmentos de línea) del cuadrilátero y determinar si se intersecan o no.
Consulte la figura para entender cómo determinar el tipo de cuadrilátero:
Cuadrilátero convexo:
La línea AB y la línea DC no se intersecan . La
línea AD y la línea BC no se intersecan. La
línea AC y la línea BD se intersecan
, por lo que el número total de intersecciones = 1
cuadrilátero cóncavo
La línea AB y la línea DC no se intersecan . La
línea AD y la línea BC no se intersecan. La
línea AC y la línea BD no se intersecan
, por lo que el número total de intersecciones = 0
si no de intersección = 1, es un cuadrilátero convexo entonces no de posibilidades = 1
si no de intersección = 0, es un cuadrilátero cóncavo entonces no de posibilidades = 3
C++
// C++ implementation of above approach
#include <iostream>
using namespace std;
struct Point // points
{
int x;
int y;
};
// determines the orientation of points
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0)
return 0;
return (val > 0) ? 1 : 2;
}
// check whether the distinct line segments intersect
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
if (o1 != o2 && o3 != o4)
return true;
return false;
}
// check if points overlap(similar)
bool similar(Point p1, Point p2)
{
// it is same, we are returning false because
// quadrilateral is not possible in this case
if (p1.x == p2.x && p1.y == p2.y)
return false;
// it is not same, So there is a
// possibility of a quadrilateral
return true;
}
// check for collinearity
bool collinear(Point p1, Point p2, Point p3)
{
int x1 = p1.x, y1 = p1.y;
int x2 = p2.x, y2 = p2.y;
int x3 = p3.x, y3 = p3.y;
// it is collinear, we are returning false
// because quadrilateral is not possible in this case
if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2))
return false;
// it is not collinear, So there
// is a possibility of a quadrilateral
else
return true;
}
int no_of_quads(Point p1, Point p2, Point p3, Point p4)
{
// ** Checking for cases where no quadrilateral = 0 **
// check if any of the points are same
bool same = true;
same = same & similar(p1, p2);
same = same & similar(p1, p3);
same = same & similar(p1, p4);
same = same & similar(p2, p3);
same = same & similar(p2, p4);
same = same & similar(p3, p4);
// similar points exist
if (same == false)
return 0;
// check for collinearity
bool coll = true;
coll = coll & collinear(p1, p2, p3);
coll = coll & collinear(p1, p2, p4);
coll = coll & collinear(p1, p3, p4);
coll = coll & collinear(p2, p3, p4);
// points are collinear
if (coll == false)
return 0;
//** Checking for cases where no of quadrilaterals= 1 or 3 **
int check = 0;
if (doIntersect(p1, p2, p3, p4))
check = 1;
if (doIntersect(p1, p3, p2, p4))
check = 1;
if (doIntersect(p1, p2, p4, p3))
check = 1;
if (check == 0)
return 3;
return 1;
}
// Driver code
int main()
{
struct Point p1, p2, p3, p4;
// A =(0, 9), B = (-1, 0), C = (5, -1), D=(5, 9)
p1.x = 0, p1.y = 9;
p2.x = -1, p2.y = 0;
p3.x = 5, p3.y = -1;
p4.x = 5, p4.y = 9;
cout << no_of_quads(p1, p2, p3, p4) << endl;
// A=(0, 9), B=(-1, 0), C=(5, -1), D=(0, 3)
p1.x = 0, p1.y = 9;
p2.x = -1, p2.y = 0;
p3.x = 5, p3.y = -1;
p4.x = 0, p4.y = 3;
cout << no_of_quads(p1, p2, p3, p4) << endl;
// A=(0, 9), B=(0, 10), C=(0, 11), D=(0, 12)
p1.x = 0, p1.y = 9;
p2.x = 0, p2.y = 10;
p3.x = 0, p3.y = 11;
p4.x = 0, p4.y = 12;
cout << no_of_quads(p1, p2, p3, p4) << endl;
// A=(0, 9), B=(0, 9), C=(5, -1), D=(0, 3)
p1.x = 0, p1.y = 9;
p2.x = 0, p2.y = 9;
p3.x = 5, p3.y = -1;
p4.x = 0, p4.y = 3;
cout << no_of_quads(p1, p2, p3, p4) << endl;
return 0;
}
Java
// Java implementation of above approach
class GFG
{
static class Point // points
{
int x;
int y;
}
// determines the orientation of points
static int orientation(Point p, Point q,
Point r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0)
return 0;
return (val > 0) ? 1 : 2;
}
// check whether the distinct
// line segments intersect
static boolean doIntersect(Point p1, Point q1,
Point p2, Point q2)
{
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
if (o1 != o2 && o3 != o4)
return true;
return false;
}
// check if points overlap(similar)
static boolean similar(Point p1, Point p2)
{
// it is same, we are returning
// false because quadrilateral is
// not possible in this case
if (p1.x == p2.x && p1.y == p2.y)
return false;
// it is not same, So there is a
// possibility of a quadrilateral
return true;
}
// check for collinearity
static boolean collinear(Point p1, Point p2,
Point p3)
{
int x1 = p1.x, y1 = p1.y;
int x2 = p2.x, y2 = p2.y;
int x3 = p3.x, y3 = p3.y;
// it is collinear, we are returning
// false because quadrilateral is not
// possible in this case
if ((y3 - y2) *
(x2 - x1) == (y2 - y1) *
(x3 - x2))
return false;
// it is not collinear, So there
// is a possibility of a quadrilateral
else
return true;
}
static int no_of_quads(Point p1, Point p2,
Point p3, Point p4)
{
// Checking for cases where
// no quadrilateral = 0
// check if any of the
// points are same
boolean same = true;
same = same & similar(p1, p2);
same = same & similar(p1, p3);
same = same & similar(p1, p4);
same = same & similar(p2, p3);
same = same & similar(p2, p4);
same = same & similar(p3, p4);
// similar points exist
if (same == false)
return 0;
// check for collinearity
boolean coll = true;
coll = coll & collinear(p1, p2, p3);
coll = coll & collinear(p1, p2, p4);
coll = coll & collinear(p1, p3, p4);
coll = coll & collinear(p2, p3, p4);
// points are collinear
if (coll == false)
return 0;
// Checking for cases where
// no of quadrilaterals= 1 or 3
int check = 0;
if (doIntersect(p1, p2, p3, p4))
check = 1;
if (doIntersect(p1, p3, p2, p4))
check = 1;
if (doIntersect(p1, p2, p4, p3))
check = 1;
if (check == 0)
return 3;
return 1;
}
// Driver code
public static void main(String args[])
{
Point p1, p2, p3, p4;
p1 = new Point();
p2 = new Point();
p3 = new Point();
p4 = new Point();
// A =(0, 9), B = (-1, 0),
// C = (5, -1), D=(5, 9)
p1.x = 0; p1.y = 9;
p2.x = -1; p2.y = 0;
p3.x = 5; p3.y = -1;
p4.x = 5; p4.y = 9;
System.out.println(no_of_quads(p1, p2, p3, p4));
// A=(0, 9), B=(-1, 0),
// C=(5, -1), D=(0, 3)
p1.x = 0; p1.y = 9;
p2.x = -1; p2.y = 0;
p3.x = 5; p3.y = -1;
p4.x = 0; p4.y = 3;
System.out.println(no_of_quads(p1, p2, p3, p4));
// A=(0, 9), B=(0, 10),
// C=(0, 11), D=(0, 12)
p1.x = 0; p1.y = 9;
p2.x = 0; p2.y = 10;
p3.x = 0; p3.y = 11;
p4.x = 0; p4.y = 12;
System.out.println(no_of_quads(p1, p2, p3, p4));
// A=(0, 9), B=(0, 9),
// C=(5, -1), D=(0, 3)
p1.x = 0; p1.y = 9;
p2.x = 0; p2.y = 9;
p3.x = 5; p3.y = -1;
p4.x = 0; p4.y = 3;
System.out.println(no_of_quads(p1, p2, p3, p4));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python implementation of above approach class Point: # points def __init__(self, x, y): self.x = x self.y = y # determines the orientation of points def orientation(p, q, r): val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) if val == 0: return 0 if val > 0: return 1 else: return 2 # check whether the distinct line segments intersect def doIntersect(p1, q1, p2, q2): o1 = orientation(p1, q1, p2) o2 = orientation(p1, q1, q2) o3 = orientation(p2, q2, p1) o4 = orientation(p2, q2, q1) if o1 != o2 and o3 != o4: return True return False # check if points overlap(similar) def similar(p1, p2): # it is same, we are returning false because # quadrilateral is not possible in this case if (p1.x == p2.x and p1.y == p2.y): return False # it is not same, So there is a # possibility of a quadrilateral return True # check for collinearity def collinear(p1, p2, p3): x1 = p1.x y1 = p1.y x2 = p2.x y2 = p2.y x3 = p3.x y3 = p3.y # it is collinear, we are returning false # because quadrilateral is not possible in this case if (y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2): return False # it is not collinear, So there # is a possibility of a quadrilateral else: return True def no_of_quads(p1, p2, p3, p4): # ** Checking for cases where no quadrilateral = 0 ** # check if any of the points are same same = True same = same & similar(p1, p2) same = same & similar(p1, p3) same = same & similar(p1, p4) same = same & similar(p2, p3) same = same & similar(p2, p4) same = same & similar(p3, p4) # similar points exist if (same == False): return 0 # check for collinearity coll = True coll = coll & collinear(p1, p2, p3) coll = coll & collinear(p1, p2, p4) coll = coll & collinear(p1, p3, p4) coll = coll & collinear(p2, p3, p4) # points are collinear if (coll == False): return 0 # ** Checking for cases where no of quadrilaterals= 1 or 3 ** check = 0 if doIntersect(p1, p2, p3, p4): check = 1 if doIntersect(p1, p3, p2, p4): check = 1 if doIntersect(p1, p2, p4, p3): check = 1 if (check == 0): return 3 return 1 # Driver code # A =(0, 9), B = (-1, 0), C = (5, -1), D=(5, 9) p1 = Point(0, 9) p2 = Point(-1, 0) p3 = Point(5, -1) p4 = Point(5, 9) print(no_of_quads(p1, p2, p3, p4)) # A=(0, 9), B=(-1, 0), C=(5, -1), D=(0, 3) p1 = Point(0, 9) p2 = Point(-1, 0) p3 = Point(5, -1) p4 = Point(0, 3) print(no_of_quads(p1, p2, p3, p4)) # A=(0, 9), B=(0, 10), C=(0, 11), D=(0, 12) p1 = Point(0, 9) p2 = Point(0, 10) p3 = Point(0, 11) p4 = Point(0, 12) print(no_of_quads(p1, p2, p3, p4)) # A=(0, 9), B=(0, 9), C=(5, -1), D=(0, 3) p1 = Point(0, 9) p2 = Point(0, 9) p3 = Point(5, -1) p4 = Point(0, 3) print(no_of_quads(p1, p2, p3, p4)) # The code is contributed by Nidhi goel
C#
// C# implementation of above approach
using System;
class GFG
{
public class Point // points
{
public int x;
public int y;
}
// determines the orientation of points
static int orientation(Point p, Point q,
Point r)
{
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0)
return 0;
return (val > 0) ? 1 : 2;
}
// check whether the distinct
// line segments intersect
static bool doIntersect(Point p1, Point q1,
Point p2, Point q2)
{
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
if (o1 != o2 && o3 != o4)
return true;
return false;
}
// check if points overlap(similar)
static bool similar(Point p1, Point p2)
{
// it is same, we are returning
// false because quadrilateral is
// not possible in this case
if (p1.x == p2.x && p1.y == p2.y)
return false;
// it is not same, So there is a
// possibility of a quadrilateral
return true;
}
// check for collinearity
static bool collinear(Point p1, Point p2,
Point p3)
{
int x1 = p1.x, y1 = p1.y;
int x2 = p2.x, y2 = p2.y;
int x3 = p3.x, y3 = p3.y;
// it is collinear, we are returning
// false because quadrilateral is not
// possible in this case
if ((y3 - y2) *
(x2 - x1) == (y2 - y1) *
(x3 - x2))
return false;
// it is not collinear, So there
// is a possibility of a quadrilateral
else
return true;
}
static int no_of_quads(Point p1, Point p2,
Point p3, Point p4)
{
// Checking for cases where
// no quadrilateral = 0
// check if any of the
// points are same
bool same = true;
same = same & similar(p1, p2);
same = same & similar(p1, p3);
same = same & similar(p1, p4);
same = same & similar(p2, p3);
same = same & similar(p2, p4);
same = same & similar(p3, p4);
// similar points exist
if (same == false)
return 0;
// check for collinearity
bool coll = true;
coll = coll & collinear(p1, p2, p3);
coll = coll & collinear(p1, p2, p4);
coll = coll & collinear(p1, p3, p4);
coll = coll & collinear(p2, p3, p4);
// points are collinear
if (coll == false)
return 0;
// Checking for cases where
// no of quadrilaterals= 1 or 3
int check = 0;
if (doIntersect(p1, p2, p3, p4))
check = 1;
if (doIntersect(p1, p3, p2, p4))
check = 1;
if (doIntersect(p1, p2, p4, p3))
check = 1;
if (check == 0)
return 3;
return 1;
}
// Driver code
static void Main()
{
Point p1, p2, p3, p4;
p1 = new Point();
p2 = new Point();
p3 = new Point();
p4 = new Point();
// A =(0, 9), B = (-1, 0),
// C = (5, -1), D=(5, 9)
p1.x = 0; p1.y = 9;
p2.x = -1; p2.y = 0;
p3.x = 5; p3.y = -1;
p4.x = 5; p4.y = 9;
Console.WriteLine(no_of_quads(p1, p2, p3, p4));
// A=(0, 9), B=(-1, 0),
// C=(5, -1), D=(0, 3)
p1.x = 0; p1.y = 9;
p2.x = -1; p2.y = 0;
p3.x = 5; p3.y = -1;
p4.x = 0; p4.y = 3;
Console.WriteLine(no_of_quads(p1, p2, p3, p4));
// A=(0, 9), B=(0, 10),
// C=(0, 11), D=(0, 12)
p1.x = 0; p1.y = 9;
p2.x = 0; p2.y = 10;
p3.x = 0; p3.y = 11;
p4.x = 0; p4.y = 12;
Console.WriteLine(no_of_quads(p1, p2, p3, p4));
// A=(0, 9), B=(0, 9),
// C=(5, -1), D=(0, 3)
p1.x = 0; p1.y = 9;
p2.x = 0; p2.y = 9;
p3.x = 5; p3.y = -1;
p4.x = 0; p4.y = 3;
Console.WriteLine(no_of_quads(p1, p2, p3, p4));
}
}
// This code is contributed by mits
Javascript
<script>
// JavaScript implementation of above approach
class Point // points
{
constructor()
{
this.x=0;
this.y=0;
}
}
// determines the orientation of points
function orientation(p,q,r)
{
let val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0)
return 0;
return (val > 0) ? 1 : 2;
}
// check whether the distinct
// line segments intersect
function doIntersect(p1,q1,p2,q2)
{
let o1 = orientation(p1, q1, p2);
let o2 = orientation(p1, q1, q2);
let o3 = orientation(p2, q2, p1);
let o4 = orientation(p2, q2, q1);
if (o1 != o2 && o3 != o4)
return true;
return false;
}
// check if points overlap(similar)
function similar(p1,p2)
{
// it is same, we are returning
// false because quadrilateral is
// not possible in this case
if (p1.x == p2.x && p1.y == p2.y)
return false;
// it is not same, So there is a
// possibility of a quadrilateral
return true;
}
// check for collinearity
function collinear(p1,p2,p3)
{
let x1 = p1.x, y1 = p1.y;
let x2 = p2.x, y2 = p2.y;
let x3 = p3.x, y3 = p3.y;
// it is collinear, we are returning
// false because quadrilateral is not
// possible in this case
if ((y3 - y2) *
(x2 - x1) == (y2 - y1) *
(x3 - x2))
return false;
// it is not collinear, So there
// is a possibility of a quadrilateral
else
return true;
}
function no_of_quads(p1,p2,p3,p4)
{
// Checking for cases where
// no quadrilateral = 0
// check if any of the
// points are same
let same = true;
same = same & similar(p1, p2);
same = same & similar(p1, p3);
same = same & similar(p1, p4);
same = same & similar(p2, p3);
same = same & similar(p2, p4);
same = same & similar(p3, p4);
// similar points exist
if (same == false)
return 0;
// check for collinearity
let coll = true;
coll = coll & collinear(p1, p2, p3);
coll = coll & collinear(p1, p2, p4);
coll = coll & collinear(p1, p3, p4);
coll = coll & collinear(p2, p3, p4);
// points are collinear
if (coll == false)
return 0;
// Checking for cases where
// no of quadrilaterals= 1 or 3
let check = 0;
if (doIntersect(p1, p2, p3, p4))
check = 1;
if (doIntersect(p1, p3, p2, p4))
check = 1;
if (doIntersect(p1, p2, p4, p3))
check = 1;
if (check == 0)
return 3;
return 1;
}
// Driver code
let p1, p2, p3, p4;
p1 = new Point();
p2 = new Point();
p3 = new Point();
p4 = new Point();
// A =(0, 9), B = (-1, 0),
// C = (5, -1), D=(5, 9)
p1.x = 0; p1.y = 9;
p2.x = -1; p2.y = 0;
p3.x = 5; p3.y = -1;
p4.x = 5; p4.y = 9;
document.write(no_of_quads(p1, p2, p3, p4)+"<br>");
// A=(0, 9), B=(-1, 0),
// C=(5, -1), D=(0, 3)
p1.x = 0; p1.y = 9;
p2.x = -1; p2.y = 0;
p3.x = 5; p3.y = -1;
p4.x = 0; p4.y = 3;
document.write(no_of_quads(p1, p2, p3, p4)+"<br>");
// A=(0, 9), B=(0, 10),
// C=(0, 11), D=(0, 12)
p1.x = 0; p1.y = 9;
p2.x = 0; p2.y = 10;
p3.x = 0; p3.y = 11;
p4.x = 0; p4.y = 12;
document.write(no_of_quads(p1, p2, p3, p4)+"<br>");
// A=(0, 9), B=(0, 9),
// C=(5, -1), D=(0, 3)
p1.x = 0; p1.y = 9;
p2.x = 0; p2.y = 9;
p3.x = 5; p3.y = -1;
p4.x = 0; p4.y = 3;
document.write(no_of_quads(p1, p2, p3, p4)+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 3 0 0
Publicación traducida automáticamente
Artículo escrito por agnivakolay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA