Question

How to check if given four points form a square in C++

Answer 1

#include <vector>
#include <iostream>
#include <algorithm> // sort

// Function to calculate the squared distance between two points
int distanceSquared(std::pair<int, int> p1, std::pair<int, int> p2) {
    return (p1.first - p2.first) * (p1.first - p2.first) +
           (p1.second - p2.second) * (p1.second - p2.second);
}

// Function to check if four points form a square
bool isSquare(std::pair<int, int> p1, std::pair<int, int> p2, std::pair<int, int> p3, std::pair<int, int> p4) {
    std::vector<int> distances = {
        distanceSquared(p1, p2), distanceSquared(p1, p3), distanceSquared(p1, p4),
        distanceSquared(p2, p3), distanceSquared(p2, p4), distanceSquared(p3, p4)
    };

    // Sort distances to group equal ones
    sort(distances.begin(), distances.end());

    // Check conditions for a square
    return distances[0] > 0 && // Non-zero side length
           distances[0] == distances[1] && distances[1] == distances[2] && distances[2] == distances[3] && // Four equal sides
           distances[4] == distances[5] && // Two equal diagonals
           distances[4] == 2 * distances[0]; // Diagonal is √2 times the side length
}

int main() {
    std::pair<int, int> p1 = {0, 0}, p2 = {0, 2}, p3 = {2, 0}, p4 = {2, 2};

    if (isSquare(p1, p2, p3, p4)) {
        std::cout << "The points form a square." << std::endl;
    } else {
        std::cout << "The points do not form a square." << std::endl;
    }
}



/*
run:

The points form a square.

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <algorithm> // sort
#include <array>
#include <iostream>
#include <vector>
#include <stdexcept>

/*
    Program: Check whether four 2D points form a square.

    Architecture notes:
    -------------------
    - The solution is built around small, focused functions.
    - We compute all pairwise distances between the four points.
    - A valid square has:
        * 4 equal side lengths
        * 2 equal diagonal lengths
        * diagonal_length == 2 * side_length
    - Distances are squared to avoid unnecessary sqrt calls and floating-point drift.
      Squared distances preserve ordering and equality checks.

    Performance notes:
    ------------------
    - O(1) time: only 6 distance computations.
    - O(1) memory: fixed-size arrays.
    - No dynamic allocations except small std::vector in main for test cases.
    - Using squared distances avoids expensive sqrt operations.

    Security notes:
    ---------------
    - Input is controlled inside main; no external input parsing.
    - Functions validate assumptions where appropriate.

    Pitfalls:
    ---------
    - Floating-point comparisons: squared distances are integers if coordinates are integers.
      If using floating-point coordinates, consider using an epsilon comparison.
    - Degenerate cases: repeated points, collinear points, or zero-area shapes.

    Tests:
    ------
    - Multiple test cases in main cover:
        * Perfect square
        * Rectangle (not square)
        * Rhombus (not square)
        * Random non-square quadrilateral
        * Duplicate points (invalid)
        * Points forming a rotated square
*/


// Represents a 2D point.
struct Point {
    double x;
    double y;
};

// Compute squared Euclidean distance between two points.
// Using squared distance avoids sqrt and floating-point noise.
double squaredDistance(const Point& a, const Point& b) {
    const double dx = a.x - b.x;
    const double dy = a.y - b.y;
    return dx * dx + dy * dy;
}

// Check whether four points form a square.
// Throws std::invalid_argument if points are degenerate.
bool isSquare(const std::array<Point, 4>& pts) {
    // Compute all 6 pairwise squared distances.
    std::array<double, 6> dists;
    int idx = 0;

    for (int i = 0; i < 4; ++i) {
        for (int j = i + 1; j < 4; ++j) {
            double d = squaredDistance(pts[i], pts[j]);
            if (d == 0.0) {
                // Degenerate: two identical points.
                throw std::invalid_argument("Two points coincide; cannot form a square.");
            }
            dists[idx++] = d;
        }
    }

    // Sort distances so we can classify them.
    std::sort(dists.begin(), dists.end());

    // After sorting:
    // dists[0..3] should be equal (sides)
    // dists[4..5] should be equal (diagonals)
    // diagonal = 2 * side
    const double side = dists[0];
    const double diag = dists[4];

    // Check 4 equal sides
    for (int i = 1; i < 4; ++i) {
        if (dists[i] != side) {
            return false;
        }
    }

    // Check 2 equal diagonals
    if (dists[4] != dists[5]) {
        return false;
    }

    // Check diagonal relationship
    // For a square: diagonal^2 = 2 * side^2
    // But since we use squared distances:
    // diag = 2 * side
    if (diag != 2 * side) {
        return false;
    }

    return true;
}

int main() {
    // Test cases
    std::vector<std::array<Point, 4>> tests = {

        // 1. Perfect axis-aligned square
        {{
            {0, 0}, {1, 0}, {1, 1}, {0, 1}
        }},

        // 2. Rectangle (not square)
        {{
            {0, 0}, {2, 0}, {2, 1}, {0, 1}
        }},

        // 3. Rhombus (equal sides but not right angles)
        {{
            {0, 0}, {2, 1}, {4, 0}, {2, -1}
        }},

        // 4. Random quadrilateral
        {{
            {0, 0}, {3, 1}, {4, 4}, {1, 3}
        }},

        // 5. Duplicate points (invalid)
        {{
            {0, 0}, {0, 0}, {1, 1}, {1, 0}
        }},

        // 6. Rotated square
        {{
            {1, 1}, {2, 2}, {1, 3}, {0, 2}
        }}
    };

    for (size_t i = 0; i < tests.size(); ++i) {
        std::cout << "Test case " << i + 1 << ": ";
        try {
            bool result = isSquare(tests[i]);
            std::cout << (result ? "Square" : "Not square") << "\n";
        } catch (const std::exception& ex) {
            std::cout << "Error: " << ex.what() << "\n";
        }
    }
}


/*
run:

Test case 1: Square
Test case 2: Not square
Test case 3: Not square
Test case 4: Not square
ERROR!
Test case 5: Error: Two points coincide; cannot form a square.
Test case 6: Square

*/

 

70+ SQL courses for beginners and professionals