Given set of N points/Co-ordinates [(x1,y1),(x2,y2), (x3,y3), (x4,y4), (x5,y5)...] find if any of them form square.

Question

Given a million list of co-ordinates in the form of longitude and latitude just as Google maps. How will you print closest k cities to a given location .

Answer 1

I tried something over here.
Probably not the best solution but it does the job. I left a few comments in the code.
Hope it helps!

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <math.h>

#define boolean int
#define true 1
#define false 0
#define DATA_SET_SIZE 5    

// structures
struct Coordinate
{
    double x;
    double y;
};    

// function prototypes
boolean containSquare(const struct Coordinate* coordinates, const int number_of_coordinates);

// main
void main(){
    int i;

    // square shape occurs in the data set
    struct Coordinate* useCaseOne = (struct Coordinate*)malloc(sizeof(struct Coordinate) * DATA_SET_SIZE); 

    useCaseOne[4].x = 1;
    useCaseOne[4].y = 2;

    useCaseOne[3].x = 1;
    useCaseOne[3].y = 4;

    useCaseOne[2].x = 3;
    useCaseOne[2].y = 2;

    useCaseOne[1].x = 3;
    useCaseOne[1].y = 4;

    useCaseOne[0].x = 4;
    useCaseOne[0].y = 5;

    printf("\nFirst data set: \n");
    for (i = 0; i < DATA_SET_SIZE; ++i)
        printf(" %3.3lf   %3.3lf \n", useCaseOne[i].x, useCaseOne[i].y);

    if (containSquare(useCaseOne, DATA_SET_SIZE) == true)
        printf("\t\tContains a square.\n");
    else
        printf("\t\tDoesn't contain a square.\n"); 

    // square shape doesn't occur in the data set
    struct Coordinate* useCaseTwo = (struct Coordinate*)malloc(sizeof(struct Coordinate) * DATA_SET_SIZE); 
    for (i = 0; i < DATA_SET_SIZE; ++i)
    {
        useCaseTwo[i].x = i;
        useCaseTwo[i].y = i;
    }

    printf("\n\nSecond data set: \n");

    for (i = 0; i < DATA_SET_SIZE; ++i)
        printf(" %3.3lf   %3.3lf \n", useCaseTwo[i].x, useCaseTwo[i].y);

    if (containSquare(useCaseTwo, DATA_SET_SIZE) == true)
        printf("\t\tContains a square.\n");
    else
        printf("\t\tDoesn't contain a square.\n");

    //exit
    printf("\n\nPress any key to exit...\n");
    _getch();

}

// function bodies
boolean containSquare(const struct Coordinate* coordinates, const int number_of_coordinates) {
    int i, j, k, m;
    double squareSideSize = 0;
    struct Coordinate A,B,C,D; // corners of the square

    if (coordinates != NULL && number_of_coordinates >= 4)
    {
        for (i = 0; i < number_of_coordinates-1; ++i)
        {
            A.x = coordinates[i].x;
            A.y = coordinates[i].y;

            for (j = 0; j < number_of_coordinates; ++j)
            {
                // all coordinates must be checked with one another, regardless of order, so we must begin the loops from 0 every time and skip coordinates we are already working with (A,B,C,D)
                if (j == i && ((j+1) < number_of_coordinates))
                    j++;

                B.x = coordinates[j].x;
                B.y = coordinates[j].y;

                if (A.x == B.x && A.y != B.y) // found vertical line
                {
                    squareSideSize = abs(A.y - B.y); // determining the size of one square side

                    for (k = 0; k < number_of_coordinates; ++k)
                    {
                        while ((k == i || k == j) && ((k+1) < number_of_coordinates))
                        k++;

                        C.x = coordinates[k].x;
                        C.y = coordinates[k].y;

                        if (C.y == A.y || C.y == B.y ) // found new corner
                        {
                            if (abs(C.x - A.x) == squareSideSize) //rectangle or square ?
                            {

                                for (m = 0; m < number_of_coordinates; ++m)
                                {
                                    while ((m == i || m == j || m == k) && ((m+1) < number_of_coordinates))
                                    m++;

                                    D.x = coordinates[m].x;
                                    D.y = coordinates[m].y;

                                    if ( ((D.x == C.x) && (D.y == B.y)) || 
                                        ((D.x == B.x) && (D.y == C.y)) )  //found last corner
                                        return true;
                                }
                            }
                        }
                    }
                }
                else if (A.y == B.y && A.x != B.x) //found horizontal line
                {
                    squareSideSize = abs(A.x - B.x); 

                    for (k = 0; k < number_of_coordinates; ++k)
                    {
                        while ((k == i || k == j) && ((k+1) < number_of_coordinates))
                        k++;

                        C.x = coordinates[k].x;
                        C.y = coordinates[k].y;

                        if (C.x == A.x || C.x == B.x) 
                        {
                            if (abs(C.y - A.y) == squareSideSize) 
                            {
                                for (m = 0; m < number_of_coordinates; ++m)
                                {
                                    while ((m == i || m == j || m == k) && ((m+1) < number_of_coordinates))
                                    m++;

                                    D.x = coordinates[m].x;
                                    D.y = coordinates[m].y;

                                    if ( ((D.x == C.x) && (D.y == B.y)) || 
                                        ((D.x == B.x) && (D.y == C.y)) )
                                        return true;
                                }
                            }
                        }
                    }
                }
            }
        }
    } 
    else
        return false;
}