Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 02.05.2012, 22:38   #1
zoha
Новичок
Джуниор
 
Регистрация: 05.04.2012
Сообщений: 2
По умолчанию Множества точек на плоскости

(Delphi)
Даны два множества точек на плоскости. Из первого множеств
выбрать три различные точки так, чтобы треугольник с вершинами
этих точках содержал (строго внутри себя) равное количества точек
первого и второго множеств.

Последний раз редактировалось zoha; 02.05.2012 в 23:01.
zoha вне форума Ответить с цитированием
Старый 02.05.2012, 23:32   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

Задача далеко не тривиальная. Отсутствие каких либо точек внутри треугольника является решением? И тех и тех по нулю, одинаковое количество. А если существует прямая делящая плоскость так, что точки одного множества по одну сторону, а другого по другую, то только и существует выше приведенное решение. А если в одном множестве только три точки не лежащие на одной прямой, а в треугольнике который они образуют лежит единственная точка второго множества, то решения вообще нет. На первый взгляд не вижу решения кроме метода тыка, то есть простым перебором возможных треугольников с подсчетом точек попадающих в середину
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 03.05.2012, 00:29   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

Цитата:
то есть простым перебором возможных треугольников с подсчетом точек попадающих в середину
я на 99.9% уверен, что авторы данной задачи именно такое решение и ожидают.

zoha, воспользуйтесь поиском.
на форуме были задачи, как перебрать по три все точки множества.

ну а проверить точки на возможность построения треугольника, найти количество точек первого и второго множества, которые в этот треугольник попадают - это уже вообще элементарно (и примеры кода проверяющего, попадает точка в треугольник или нет - тоже есть тут, на форуме). соберёте это "в кучу" - получите решение задачи.

p.s. и я согласен с Аватар - если не подобрать множества точек особым образом, то для случайных наборов программа почти всегда будет говорить о том, что нет такого треугольника, куда бы попало одинаковое (и не нулевое) число точек 1-го и 2-го множеств!
Serge_Bliznykov вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программа. Даны 2 множества точек на плоскости - найти те три, которые образуют нужный треугольник ( C++ ) anya4363 Помощь студентам 0 06.02.2012 13:44
Даны координаты n точек на плоскости. Найти номера двух точек, расстояние между которыми наибольшее. Viwwna Паскаль, Turbo Pascal, PascalABC.NET 2 19.11.2011 06:33
Перечислить точки заданного множества точек на плоскости в соответствии с этим порядком dark999 Помощь студентам 0 02.04.2011 18:35
Перечислить точки заданного множества точек на плоскости dark999 Помощь студентам 4 01.04.2011 23:50
множества точек на плоскости TachOn Фриланс 6 20.01.2010 18:30