@ДмитрийЛар

Здравствуйте! Есть задача. Задано множество точек на плоскости. Найти все четверки точек, являющихся вершинами квадратов. Найти квадрат, внутри которого лежит наибольшее количество точек множества. С поиском четвёрок всё понятно - сравнить длины сторон и проверить скалярное произведение. А вот как определить лежит ли точка внутри квадрата или нет сложновато. Нашел здесь в темах программу от Puporeva на Pascale с комментариями, вроде всё понятно. Стал пробовать в MathCADe на простых примерах не всё сходится. Идея заключается в нахождении площади треугольников и сравнении попарного их произведения с нулём (если два произведения больше нуля, то точка принадлежит квадрату). На простых примерах получил, что, если одно произведение равно нулю, то точка лежит на стороне квадрата, а значит и принадлежит ему. И ещё, если произведения попарно отрицательны, то тоже находится внутри. Пример свой прикрепляю с программой Puporeva. Может кто-то знает это правило про точку внутри треугольников или есть ещё какой способ, чтобы можно алгоритм было составить?

Вложения

tochka v kvadrate.zip (13.2 Кб, 10 просмотров)

0

@Symon

Используйте это

1

@ДмитрийЛар

Symon, спасибо! написал кое-что. Вроде правильно, но нашел ошибку при расчётах. Задаю 7точек так, чтобы получалось 3квадрата и одна точка внутри одного из квадратов. Но находит только 2квадрата, а один не находится, потому что точки в массиве идут по диагонали (проверил простым введением точек и вычислением определителей векторов вначале программы). Может нужно как-то изменить формулу или перебор в цикле? И в ответе не отображаются координаты точек вершин квадрата. Можете подсказать в чём причина?

Вложения

kvadrat.zip (25.4 Кб, 21 просмотров)

0

@Symon

Квадраты теряются из-за неправильной организации границ циклов. Не все варианты прощупываются.
В приложении полное решение задачи с квадратами:

Найти все квадраты с вершинами в точках данного множества. Определить число точек множества, входящих в каждый квадрат.
Квадраты.zip

1

@ДмитрийЛар

Symon, можете в формате mcd скинуть, а то у меня маткад11?

0

@Symon

Квадраты.zip

1

@ДмитрийЛар

Symon, спасибо большое! Преподаватель принял и первоначальный ещё мой вариант. Зато теперь понял как проверить точки по диагонали или нет.

0