Comprueba si cuatro segmentos forman un rectángulo.

Nos dan cuatro segmentos como un par de coordenadas de sus puntos finales. Necesitamos decir si esos cuatro segmentos de línea forman un rectángulo o no. 
Ejemplos: 
 

Input : segments[] =  [(4, 2), (7, 5),
                       (2, 4), (4, 2),
                       (2, 4), (5, 7),
                       (5, 7), (7, 5)]
Output : Yes
Given these segment make a rectangle of length 3X2.

Input : segment[] = [(7, 0), (10, 0),
                     (7, 0), (7, 3),
                     (7, 3), (10, 2),
                     (10, 2), (10, 0)]
Output : Not
These segments do not make a rectangle.

Above examples are shown in below diagram.

Este problema es principalmente una extensión de Cómo verificar si dados cuatro puntos forman un cuadrado
 

Podemos resolver este problema usando las propiedades de un rectángulo. Primero, verificamos los puntos finales únicos totales de los segmentos, si el recuento de estos puntos no es igual a 4, entonces el segmento de línea no puede formar un rectángulo. Luego verificamos las distancias entre todos los pares de puntos, debe haber como máximo 3 distancias diferentes, una para la diagonal y dos para los lados y al final verificaremos la relación entre estas tres distancias, para que los segmentos de línea formen un rectángulo, estas distancias deben satisface la relación de Pitágoras porque los lados y la diagonal del rectángulo forman un triángulo rectángulo. Si cumplen las condiciones mencionadas, marcaremos el polígono formado por segmento de línea como rectángulo, de lo contrario no.
 

// C++ program to check whether it is possible
// to make a rectangle from 4 segments
#include <bits/stdc++.h>
using namespace std;
#define N 4
 
// structure to represent a segment
struct Segment
{
    int ax, ay;
    int bx, by;
};
 
// Utility method to return square of distance
// between two points
int getDis(pair<int, int> a, pair<int, int> b)
{
    return (a.first - b.first)*(a.first - b.first) +
        (a.second - b.second)*(a.second - b.second);
}
 
// method returns true if line Segments make
// a rectangle
bool isPossibleRectangle(Segment segments[])
{
    set< pair<int, int> > st;
 
    // putting all end points in a set to
    // count total unique points
    for (int i = 0; i < N; i++)
    {
        st.insert(make_pair(segments[i].ax, segments[i].ay));
        st.insert(make_pair(segments[i].bx, segments[i].by));
    }
 
    // If total unique points are not 4, then
    // they can't make a rectangle
    if (st.size() != 4)
        return false;
 
    // dist will store unique 'square of distances'
    set<int> dist;
 
    // calculating distance between all pair of
    // end points of line segments
    for (auto it1=st.begin(); it1!=st.end(); it1++)
        for (auto it2=st.begin(); it2!=st.end(); it2++)
            if (*it1 != *it2)
                dist.insert(getDis(*it1, *it2));
 
    // if total unique distance are more than 3,
    // then line segment can't make a rectangle
    if (dist.size() > 3)
        return false;
 
    // copying distance into array. Note that set maintains
    // sorted order.
    int distance[3];
    int i = 0;
    for (auto it = dist.begin(); it != dist.end(); it++)
        distance[i++] = *it;
 
    // If line seqments form a square
    if (dist.size() == 2)
    return (2*distance[0] == distance[1]);
 
    // distance of sides should satisfy pythagorean
    // theorem
    return (distance[0] + distance[1] == distance[2]);
}
 
// Driver code to test above methods
int main()
{
    Segment segments[] =
    {
        {4, 2, 7, 5},
        {2, 4, 4, 2},
        {2, 4, 5, 7},
        {5, 7, 7, 5}
    };
 
    (isPossibleRectangle(segments))?cout << "Yes\n":cout << "No\n";
}

// JavaScript program to check whether it is possible
// to make a rectangle from 4 segments
 
const N = 4;
 
// Utility method to return square of distance
// between two points
function getDis(a, b)
{
    return (parseInt(a[0]) - parseInt(b[0]))*(parseInt(a[0]) - parseInt(b[0])) + (parseInt(a[1]) - parseInt(b[1]))*(parseInt(a[1]) - parseInt(b[1]));
}
 
// method returns true if line Segments make
// a rectangle
function isPossibleRectangle(segments)
{  
    let st = new Set();
 
    // putting all end points in a set to
    // count total unique points
    for (let i = 0; i < N; i++)
    {
        let tmp1 = [segments[i][0], segments[i][1]];
        let tmp2 = [segments[i][2], segments[i][3]];
        st.add(tmp1.join(''));
        st.add(tmp2.join(''));
    }
 
    // If total unique points are not 4, then
    // they can't make a rectangle
    if (st.size != 4)
    {
        return false;
    }
         
    // dist will store unique 'square of distances'
    let dist = new Set();
 
    // calculating distance between all pair of
    // end points of line segments
    for(let it1 of st)
    {
        for(let it2 of st)
        {
            if(it1 !== it2)
            {
                dist.add(getDis(it1.split(''), it2.split('')));
            }
        }
    }
 
    // if total unique distance are more than 3,
    // then line segment can't make a rectangle
    if (dist.size > 3)
    {
        return false;
    }
         
    // copying distance into array. Note that set maintains
    // sorted order.
    let distance = new Array();
    for (let x of dist)
    {
        distance.push(x);
    }
         
    // If line seqments form a square
    if (dist.size === 2)
    {
        return (2*distance[0] == distance[1]);
    }
 
    // distance of sides should satisfy pythagorean
    // theorem
    return (distance[0] + distance[1] == distance[2]);
}
 
// Driver code to test above methods
{
    let segments = [
        [4, 2, 7, 5],
        [2, 4, 4, 2],
        [2, 4, 5, 7],
        [5, 7, 7, 5] ]
 
    if(isPossibleRectangle(segments)){
        console.log("Yes");
    }
    else{
        console.log("No");
    }
}
 
// The code is contributed by  Nidhi Goel

Producción: 
 

Yes

Complejidad de Tiempo: O(n ² logn) 
Espacio Auxiliar: O(n)

Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.