 Задача на множества |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| Justus |
 30.10.2005 20:23
Сообщение
#1
|
|
Группа: Пользователи Сообщений: 8 Пол: Мужской Репутация:  0   |
Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы треугольник с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь.
|
   |
 
|
  |
Ответов(1 - 4)
| volvo |
30.10.2005 20:28
Сообщение
#2
|
|
Гость |
To: Justus
объемы множеств какие? Если не очень большие, то полным перебором задача решается элементарно. Если большие - сложнее, будем думать... |
|
|
|
| Justus |
30.10.2005 20:35
Сообщение
#3
|
|
Группа: Пользователи Сообщений: 8 Пол: Мужской Репутация: 0 |
Про размер этих множеств речи не идет, для меня важнее всего реализация. Я вот пытаюся решить эту задачу методом площадей, когда площадь постоенных треугольников сравнивается с площадью искомого, но могут быть варианты, когда пощади вроде-бы совпадают, а вершины не накрываються, кстати а в чем заключается метод перебора?
|
|
|
|
| volvo |
30.10.2005 20:46
Сообщение
#4
|
|
Гость |
Цитата а в чем заключается метод перебора? Из первого множества последовательно выбираешь тройки вершин (алгоритм выборки ищи на форуме), и каждую точку из второго множества проверяешь, принадлежит ли она треугольнику (это тоже есть). Если все точки второго множества принадлежат этому треугольнику, то вычисляем его площадь, сравниваем с текущим минимумом, и (если вновь найденная площадь меньше предыдущей) запоминаем координаты вершин и саму площадь... То же самое повторяем для всех комбинаций вершин из первого множества, в результате получаешь либо 0 (нет таких точек), либо координаты вершин и площадь (которая является минимальной) |
|
|
|
| Justus |
30.10.2005 20:53
Сообщение
#5
|
|
Группа: Пользователи Сообщений: 8 Пол: Мужской Репутация: 0 |
Спасибо, попробую.
|
|
|
|
|
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 20.07.2025 0:51 |