математика — эффективный способ найти, если точки образуют квадрат. Переполнение стека вычислений

Я здесь новенький. Я решаю проблему, чтобы проверить, образуют ли N точек (x, y) квадрат. Окончательный результат — количество квадратов, которые могут сформировать точки + самая большая площадь (один из квадратов).
Введите как это:

6
1 1
1 2
1 3
2 3
2 2
2 1

Выход:

2 -> (2 Squares were formed)
1 -> (1 was the biggest area)

Итак, я читаю х и у вот так:

cin >> n;
for(int i=0;i<n;i++)
{cin >> coordenadas[i].x >> coordenadas[i].y;concat[i]=coordenadas[i].y * 100000 + coordenadas[i].x;}
sort (concat, concat+n);
for(int i=0;i<n;i++)
{
A.x=coordenadas[i].x;A.y=coordenadas[i].y;
for(int ii=M;ii<n;ii++)
{
B.x=coordenadas[ii].x;
B.y=coordenadas[ii].y;
...
calculo();
if(mArea<area)
mArea=area;
}
M+=1;
}

В следующей функции я пытаюсь вычислить переменную x и y, чтобы получить такие значения -> http://i.stack.imgur.com/Uqtau.png

Но я не уверен в своих расчетах.

И моя функция вычисления:

void calculo()
{
int x=0,y=0;
if(A.x==B.x)
{
x=abs(B.y-A.y);
area=x*x;
R1.c1=(B.y) * 100000 + (A.x + x);
R1.c2=(B.y) * 100000 + (A.x - x);
if (binary_search (concat, concat+n, R1.c1))
if (binary_search (concat, concat+n, R1.c2))
quadrados+=1;
else
area=0;
}
else
{
x=abs(B.y-A.y);
y=abs(B.x-A.x);
area=sqrt(x*x+y*y)*sqrt(x*x+y*y);
R1.c1=(B.y + y) * 100000 + (B.x - x);
R1.c2=(A.y + y) * 100000 + (A.x - x);
if (binary_search (concat, concat+n, R1.c1))
if (binary_search (concat, concat+n, R1.c2))
quadrados+=1;
else
area=0;
}
}

То, что я делаю, это выбираю 2 уникальные точки и вычисляю возможные две другие точки, которые образуют квадрат. затем я «объединяю» их в уникальное целое число (например, (By + y) * 100000 + (Bx — x), что означает -> y * 100000 + x), затем я ищу их с помощью двоичного поиска, если они были найдены я увеличиваю n_square var.

Проблема в том, что я не уверен, что расчет в порядке, и мне нужна помощь с этим. Я знаю, что есть способ расчета с битсетом, но я не эксперт, поэтому я не могу использовать битсет. Я пытаюсь получить решение O (N ^ 2 * log (V)). Дайте мне несколько советов

################### НОВОЕ РЕДАКТИРОВАНИЕ ПОСЛЕ НЕКОТОРЫХ КОММЕНТАРИЙ -> ###################

НОВЫЙ Ввод (Комментарий)

9
5 3
1 4
1 3
1 2
2 1
2 3
3 4
3 2
4 2

Выход:

6 (Number of Squares)
0 (Its Area-> I'm not calculating yet)

Ожидаемый результат

3
5 (Area)

Новый код:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct c{

int x,y;

}A,B,C,D,coordenadas[3001];

int quadrados=0,n=0;
long int area;
long int concat[3001];

int dist2 (c A,c B) {
int x = A.x - B.x;
int y = A.y - B.y;
return x*x + y*y;
}void calculo()
{
int d = dist2(A, B);
const int x = B.x - A.x;
const int y = B.y - A.y;
C.x = A.x - y;
C.y = A.y + x;
D.x = B.x - y;
D.y = B.y + x;
d = dist2(A, B);
if (dist2(A, C) == d && 2*d == dist2(B, C))
if (binary_search (concat, concat+n, C.y * 100000 + C.x))
if (dist2(B, D) == d && dist2(C, D) == d)
if (binary_search (concat, concat+n, D.y * 100000 + D.x))
{
quadrados+=1;
}

}

int main() {

int M=1,mArea=0;
cin >> n;
for(int i=0;i<n;i++)
{cin >> coordenadas[i].x >> coordenadas[i].y;concat[i]=coordenadas[i].y * 100000 + coordenadas[i].x;}
sort (concat, concat+n);
for(int i=0;i<n;i++)
{
A.x=coordenadas[i].x;
A.y=coordenadas[i].y;
for(int ii=M;ii<n;ii++)
{
B.x=coordenadas[ii].x;
B.y=coordenadas[ii].y;
calculo();
if(mArea<area)
mArea=area;
}
M+=1;
}

if(quadrados==0)
cout << quadrados << endl;
else
cout << quadrados << endl << mArea << endl;
return 0;
}

1

Решение

С вашей картинки:

const int x = B.x - A.x;
const int y = B.y - A.y;
C.x = A.x - y;
C.y = A.y + x;
D.x = B.x - y;
D.y = B.y + x;

затем

area = x * x + y * y;
2

Другие решения

Я предполагаю, что все координаты являются целыми числами, и выбранный вами тип может вписаться в квадрат с наибольшей координатой (800 миллионов, в вашем случае — не сложно). С последним предположением можно отказаться, если это необходимо, но с первым не все так просто, поскольку в противном случае вам пришлось бы решать, как обрабатывать округления.

Основная идея состоит в том, чтобы пройти через каждую точку A и каждую точку B, появляющуюся в списке позже, чем A. Вычислить

int dist2 (A, B) {
int x = A.x - B.x;
int y = A.y - B.y;
return x*x + y*y;
}

int d = dist2(A, B);

чтобы d это квадрат расстояния между А и В. Теперь определите

c C1, C2, D;
C1.x = 2*A.x - B.y;
C1.y = B.x;
C2.x = B.y;
C2.y = 2*A.y - B.x;

и проверьте, находится ли C1 (соответственно, C2) в списке после B. Если это так, назовите его C и проверьте,

dist2(B, D) == d && dist2(C, D) == d

Если это так, ABCD является квадратом. Если у вас есть n элементов в общей сложности, первые два цикла происходят n (n-1) / 2 раза, и каждая пара вызывает 2 или 3 поиска, показывая, что алгоритм выполняется за время O (n ^ 2 log n).

Редактировать: более ранняя версия также дала более простой алгоритм, который работал во времени O (n ^ 3). Его существование вызвало путаницу, поэтому я удалил его и сделал другой алгоритм более явным.

-1