ВУЗы и колледжи

Образуют ли 4 точки квадрат?

Имеются координаты четырёх точек (на плоскости, X и Y). Точки могут быть в произвольном порядке. Квадрат, если он есть, может быть вовсе не параллелен осям координат, а просто так, произвольный. Как определить, образуют ли они квадрат, и если да - то в какой последовательности. Последовательность - в смысле, как выстроить их, что бы соединяя по порядку вышел квадрат. Например, точки A(10,10) B(20,20) C(10,20) D(20,10) - явно квадрат. Последовательность - ADBC, например, или ACBD. Потому, что AB - диагональ квадрата, так же как и CD. Надо по координатам узнать, что это квадрат и найти порядок точек. Например, по часовой или против часовой. Подайте идею, как это можно попроще определить? Только перебором взаимной параллельности, перпендикулярности и равенства отрезков во всех комбинациях? (решаться должно на компе, но я думаю, должно всё быть проще как-то)
Попробуйте так. Находите квадраты всех попарных расстояний (6 штук) . Если среди них четыре равных, а два других равны и ровно вдвое больше (то есть шесть чисел вида s, s, s, s, 2s, 2s), то это квадрат.

A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4) — данные точки.

s1 = (x1 − x2)² + (y1 − y2)²,
s2 = (x1 − x3)² + (y1 − y3)²,
s3 = (x1 − x4)² + (y1 − y4)²,
s4 = (x2 − x3)² + (y2 − y3)²,
s5 = (x2 − x4)² + (y2 − y4)²,
s6 = (x3 − x4)² + (y3 − y4)².

(s1 = s3 = s4 = s6) & (s2 = s5 = 2s1) ⇒ ABCD — квадрат;
(s1 = s2 = s5 = s6) & (s3 = s4 = 2s1) ⇒ ABDC — квадрат;
(s2 = s3 = s4 = s5) & (s1 = s6 = 2s2) ⇒ ACBD — квадрат.

Если таки квадрат, то ориентацию можно найти, вычислив площадь как определитель (если против часовой, то будет положительный; если по часовой, — то отрицательный).
СК
Сергей Костенко
23 672
Лучший ответ
вот такая идея, если на компе
находишь расстояния любой точки до 3 остальных
находишь наибольшее расстояние - это вероятная диагональ
находишь координаты ее середины
находишь расстояние от нее до всех точек
если они равны то это квадрат
вершины на которых определенная диагональ - это 1 и 3

вообще т на компе и перебором не трудно....
Анастасия Яковенко Идея хорошая, но прямоугольник тоже подойдёт под это.
Но есть над чем подумать, спасибо!
1. Найти длины сторон и сравнить их (хотя бы 2 стороны, не содержащие общую точку) .
2. Найти 2 скалярных произведения векторов, содержащих общую точку (проверить на равенство 0).
ИЛ
Игорь Ларин
1 691

Похожие вопросы