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

pastorixx

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

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

pastorixx

Active member
07.05.2010
26
0
#2
Так как это квадрат, то разность координат между двух пар вершин должна быть одинакова, угол пока не учитывал, так как не знаю как(
Можете кто нибудь псевдокод кинуть, с учетом угла? Подозреваю в своем коде ошибку(
Вот что я написал:
Код:
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)
{
A = new double[2, N];
double[,] B = new double[2,N];
int[,] x = new int[2,N];
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 = 1; i < N; i++)
{
B[0,i] = A[0, i-1] - A[0, i];
B[1, i] = A[1, i-1] - A[1, i];
}
for (int i = 0; i < N; i++)
{
for(int j = 0; j<N;j++)
if(B[0,j] == B[0,i])
if(B[1,j] == B[1,i])
textBox1.Text = "Найден квадрат, его вершины "+"("+j+","+i+")";
}



}
}
}
 

pastorixx

Active member
07.05.2010
26
0
#3
Массив 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])
{
// Попытка избавления от повтора вывода вершин квадрата 
}
}
}
}
}

private void button2_Click(object sender, EventArgs e)
{
Random r;
r = new Random();
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
dataGridView1[0, i].Value = (double)r.Next(-10, 10);
dataGridView1[1, i].Value = (double)r.Next(-10, 10);
}
}
}
}