IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Вершины квадрата, Заданы координаты, выделить вершины квадрата
сообщение
Сообщение #1


Гость






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

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

Софа
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Софья

Репутация: -  0  +


Теоретически я все понимаю, а как это реализовать конкретно в программе? Если можно, то напишите полностью программу. Буду очень признательна. Софа
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Софа @ 10.05.2007 9:39) *

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

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

klem4, я не совсем тебя понял.. Что значит:
Цитата
берем очередные две точки, (проверяем являются ли стороны построенные по этим точкам равными по длине

?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Софья

Репутация: -  0  +


Честно, я сама не понимаю условия. Речь все-таки идет о квадрате. Я так думаю, на плоскости есть множество точек. Может надо привести к квадратной матрице? А как вы думаете? Софа
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


2 точки

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

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

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

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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Софья

Репутация: -  0  +


Я сегодня постараюсь узнать
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Софья

Репутация: -  0  +


Координаты точек должны задаваться integer. Софа
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 23:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name