Вершины квадрата, Заданы координаты, выделить вершины квадрата Опции

[Софа]

Узнала о Вашем форуме и хочу, чтобы мне помогли решить такую задачу. Пожалуйста, помогите!!!

На плоскости заданы N точек с координатами (х1, у1), (х2, у2), ... , (хN, yN). Написать программу, которая из этих точек выделяет вершины квадрата, содержащего максимальное число заданных точек. (Предполагается, что точки, расположенные на сторонах квадрата принадлежат ему.)

Софа

[klem4]

1) Именно квадрат, не прямоугольник ?
2) Ну первое что приходит в голову - перебор всех пар точек, берем очередные две точки, (проверяем являются ли стороны построенные по этим точкам равными по длине (для прямоугольника проверка не нужна)), затем идем по оставшимся точкам, и смотрим входит ли данная точка в наш прямоугольник (квадрат), затем если количество вошедших точке больше текущего максимума, запоминаем новый максимум и точки на которых был построен прямоугольник (квадрат)

Сообщение отредактировано: klem4 - 9.05.2007 13:58

[Софа]

Теоретически я все понимаю, а как это реализовать конкретно в программе? Если можно, то напишите полностью программу. Буду очень признательна. Софа

[Lapp]

Теоретически я все понимаю ... Софа

Софа, пожалуйста, изложи алгоритм - или в любом другом виде - то, что ты понимаешь

klem4, я не совсем тебя понял.. Что значит:

берем очередные две точки, (проверяем являются ли стороны построенные по этим точкам равными по длине

?

[Софа]

Честно, я сама не понимаю условия. Речь все-таки идет о квадрате. Я так думаю, на плоскости есть множество точек. Может надо привести к квадратной матрице? А как вы думаете? Софа

[klem4]

klem4, я не совсем тебя понял.. Что значит:

2 точки

Левая верхняя: (0; 2)
Правая нижняя: (2; 0)

- годится, эти точки образуют квадрат

Левая верхняя: (0; 2)
Правая нижняя: (3; 0)

Не годится, это не квадрат.

[Lapp]

Klem4, как я понял, ты предполагаешь, что стороны квадрата параллельны осям координат.. Почему? В условии этого нет. Поэтому любая пара точек годится, если строить на ней квадрат, как на диагонали. После этого следует проверить остальные две вершины на принадлежность множеству. И еще нужно проверить возможность построения квадрата по этим точкам, как вершинам на одной стороне..
Короче, я бы не стал, пожалуй, рассматривать пары точек - я бы сразу рассмотрел четверки. Даже рассмотрение троек будет сложнее алгоритмически.. В любом случае, нахождение условия, являются ли данные 4 точки вершинами квадрата - отдельная песня .

Софа, как совместить эти два твои высказывания:

Теоретически я все понимаю

и

я сама не понимаю условия

- а?..
Написание программы - это на 90% - ясное понимание и алгоритм, и лишь на 10% - написание самой программы с отладкой. И если ты не можешь помочь с главным, то хотя бы не торопи с второстепенным. Внося путаницу, ты просто мешаешь нам помочь тебе.
Если ты действительно хочешь помочь, проясни, пожалуйста, условие. Выясни, в каком виде задаеются координаты точек: это integer или real? Если окажется real, то узнай, с какой точностью производить сравнение чисел. Если ты это выяснишь (как я понимаю, у преподавателя), то будет реальная польза.
Сигналь, поняла ли ты меня, или я колебал воздух впустую..

[Софа]

Я сегодня постараюсь узнать

[Софа]

Координаты точек должны задаваться integer. Софа

[klem4]

Klem4, как я понял, ты предполагаешь, что стороны квадрата параллельны осям координат..

Да, я так предполагал ... ошибочно.