Точки на плоскости, нахождение квадрата

[PastoriXx]

Такая задача:
Даны N точек на плоскости(N>=4). Выяснить, найдутся ли среди этих точек такие, которые являются вершинами квадрата. Найти стороны этого квадрата.

Можете объяснить способ нахождения вершин квадрата и его сторон?

[Sazary]

Общий принцип: у вас есть N точек с координатами x и y. Берете 4 точки и считаете расстояние между парами 1-2, 2-3, 3-4 и 4-1. Если эти расстояния равны, значит точки образуют ромб. Остается найти какой-нибудь угол и проверить, равен ли он 90 градусам. Если так, то имеем квадрат. И так нужно перебрать все комбинации 4-х точек.

[PastoriXx]

Это понятно, но вот как найти длины сторон и угол, вот это проблема.
Пока я сделал так, завел два массива, один с точками, другой с разностью между точками. Если они равны то это квадрат. Я понимаю что это далеко неправильно.

[Serge_Bliznykov]

расстояние между точками найти совсем просто:
это корень квадратный из суммы квадратов разностей координат. Поясню на примере. Расстояние между точками X1,Y1 и X2.Y2 равно :
L := SQRT( SQR(X1-X2) + SQR(Y1-Y2) )
(здесь SQR - это возведение в квадрат,
а SQRT - извлечение квадратного корня).


По поводу нахождения угла.

Можно сходить по ссылке: Полезные функции и процедуры: часть 1

3. Угол между точками

Это немного сложнее, но тоже легко - на уровне тригонометрии девятого класса. В основном используется для поворота игрока за курсором мыши и т.п.

function GetAngle(X, Y: Real): Real;
begin
  GetAngle := -(ArcSin(X / Sqrt((X * X + Y * Y))))) / PiDiv2;
end;

Следует отметить, что точка должна находиться относительно в центре координат. Таким образом, для получения угла между точками нужно подставить значения (X - X0), (Y - Y0).

а ещё можно почитать книжку:

Название: Программирование в алгоритмах
Автор: Окулов С.М.
Издательство: Бином
Год: 2002
Страниц: 341
Формат: pdf
Размер: 3,27 Mb
ISBN: 5-94774-010-9

Глава 5. Алгоритмы вычислительной геометрии
...
страница 226.
Function GetAngle(Const x, у: Real): Real;
{ *Возвращает угол от 0 до 2*Pi (в радианах) . *}

[PastoriXx]

Массив C[,] хранит номера точек которые образуют квадрат, нужно чтобы не выводило на экран повтор-ся квадраты, помогите правильно отсортировать массив, можно допустим делать флаг на повторах и не выводить на экран, но сам поиск повторов не могу написать

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Семистровая_задача_5
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        int N;
        double[,] A;
        private void numericUpDown1_ValueChanged(object sender, EventArgs e)
        {
            N = (int)numericUpDown1.Value;
            dataGridView1.RowCount = N;
            dataGridView1.ColumnCount = 2;
        }

        private void button1_Click(object sender, EventArgs e)
        {
            textBox1.Clear();
            double[] B = new double[6];
            int[,] C = new int[4,N];
            A = new double[2, N];
            int j1 = -1, t1 = -1, u1 = -1, p=0;
            for (int i = 0; i < N; i++)
            {
                A[0, i] = Convert.ToDouble(dataGridView1[0, i].Value);
                A[1, i] = Convert.ToDouble(dataGridView1[1, i].Value);
            }

            for (int i = 0; i < N; i++)
            {
                if (i != j1 && i != t1 && i != u1)
                for (int j = 0; j < N; j++)
                {
                    if (j != i && j != t1 && j != u1)
                    B[0] = Math.Sqrt((A[0, i] - A[0, j]) * (A[0, i] - A[0, j]) + (A[1, i] - A[1, j]) * (A[1, i] - A[1, j]));
                    for (int t = 0; t < N; t++)
                    {
                        if (t != i && t != j)
                        for (int u = 0; u < N; u++)
                        {
                            if (u != i && u != j && u != t)
                            {
                                B[1] = Math.Sqrt((A[0, t] - A[0, u]) * (A[0, t] - A[0, u]) + (A[1, t] - A[1, u]) * (A[1, t] - A[1, u]));
                                if (B[0] == B[1] && B[0]>0)
                                {
                                    B[2] = Math.Sqrt((A[0, i] - A[0, u]) * (A[0, i] - A[0, u]) + (A[1, i] - A[1, u]) * (A[1, i] - A[1, u]));
                                    B[3] = Math.Sqrt((A[0, j] - A[0, t]) * (A[0, j] - A[0, t]) + (A[1, j] - A[1, t]) * (A[1, j] - A[1, t]));
                                    if (B[1] == B[2] && B[1] == B[3])
                                    {
                                        B[4] = Math.Sqrt((A[0, i] - A[0, t]) * (A[0, i] - A[0, t]) + (A[1, i] - A[1, t]) * (A[1, i] - A[1, t]));
                                        B[5] = Math.Sqrt((A[0, j] - A[0, u]) * (A[0, j] - A[0, u]) + (A[1, j] - A[1, u]) * (A[1, j] - A[1, u]));
                                        if (B[4] == B[5])
                                        {
                                            C[0, p] = i; C[1, p] = j; C[2, p] = t; C[3, p] = u;
                                            p++;
                                            //textBox1.Text += "Найден квадрат, его вершины " + "А(" + A[0, i] + "," + A[1, i] + "),  " + "B(" + A[0, j] + "," + A[1, j] + "),  " + "C(" + A[0, t] + "," + A[1, t] + "),  " + "D(" + A[0, u] + "," + A[1, u] + "). " + "\r\n";
                                            j1 = j; t1 = t; u1 = u;

                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            for (int i = 0; i < 4; i++)
                for (int j = 0; j < N; j++)
                    for (int l = 0; l < N;l++)
                        if (C[0, j] == C[i, l])
                        {
                            for (i = 0; i < 4; i++)
                                if (C[1, j] == C[i, l])
                                {
                                    for (i = 0; i < 4; i++)
                                        if (C[2, j] == C[i, l])
                                        {
                                            for (i = 0; i < 4; i++)
                                                if (C[3, j] == C[i, l])
                                                {
// Попытка избавления от повтора вывода вершин квадрата 
                                                }
                                        }
                                }
                        }
        }

       
    }
}

[PastoriXx]

Я кстати обошелся без поиска угла, я просто сравниваю длины сторон, потом диагоналей, если они равны то это квадрат

[PastoriXx]

Помогите с поиском повторений!!!