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

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

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

> Четырехугольник
сообщение
Сообщение #1


Гость






Запрограммировать на Pascal:

Найти четырехугольник с вершинами в заданных точках, содержащий наибольшее число заданных точек. (Графика не нужна)

Здесь необходимо через заданные точки построить всевозможное количество четырехугольников, вычисляя количество точек, которые попадают внутрь его. Никак не могу додуматься до алгоритма построения всевозможных вариантов четырехугольника. Размышляю так: через четыре точки можно построить 24 четырехугольника, через 5 – 120, т.е. берется факториал от количества точек. Т.е. для 4 точек надо перебрать 24 комбинации, для 5 – 120. Но как это свести это в единый алгоритм? Или может, есть вариант куда проще?
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской

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


Спасибо, всем участникам. Я позавчера все-таки написал эту программу, используя алгоритм от Volvo (мои особые благодарности).
Единственное, что смущает: никак толком полностью не могу уловить смысл этой функции PointInSidebar (алгоритм работы).
Буду очень признателен, если подскажите.
Вот эта функция:
Код

Function PointInSidebar(Const SideBar: Array Of TPoint;
        p: TPoint; Count: Integer): Boolean;
 Var
   x1,y1,x2,y2: Double;
   x0, y0, sum, divisor: Double;
   i: integer;
 Begin
   sum := 0;
   y0 := p.y;
   x0 := p.x;
   For i := 0 to Pred(count-1) do
     Begin
       x1:=sidebar[i].x;
       y1:=sidebar[i].y;
       x2:=sidebar[i+1].x;
       y2:=sidebar[i+1].y;

       divisor:=y1*x2-x1*y2-y0*x2+y0*x1+x0*y2-x0*y1;
       divisor := divisor + 1.0E-10;

       Sum := sum + (
       -arctan( (-x2*x1+x1*x0+y0*y1-x2*x0+x2*x2-y2*y0+y2*y2-y1*y2 )/divisor)+
       arctan( (-x1*x1+x2*x1+x1*x0+y0*y1+y1*y2-x2*x0-y1*y1-y2*y0 )/divisor)
       );
     End;

   x1:=sidebar[count-1].x;
   y1:=sidebar[count-1].y;
   x2:=sidebar[0].x;
   y2:=sidebar[0].y;

   divisor:=y1*x2-x1*y2-y0*x2+y0*x1+x0*y2-x0*y1;
   divisor := divisor + 1.0E-10;
   Sum := sum + (
   -arctan((-x2*x1+x1*x0+y0*y1-x2*x0+x2*x2-y2*y0+y2*y2-y1*y2)/divisor)+
   arctan((-x1*x1+x2*x1+x1*x0+y0*y1+y1*y2-x2*x0-y1*y1-y2*y0)/divisor)
   );

   pointinsidebar := not (abs(Sum) < 0.0001)
 End;


Спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Andy   Четырехугольник   12.11.2004 22:07
APAL   Что то я не врубился... почему на 4-ех точках можн…   12.11.2004 22:16
Andy   Четырехугольник - это не параллелограмм или ромб. …   13.11.2004 0:16
Altair   Я тоже... если 4 точки и вершиины прямоугольника…   13.11.2004 11:17
Andy   Я же сказал, что у меня ЧЕТЫРЕХУГОЛЬНИК, а не пр…   13.11.2004 22:23
Флогримм   я вроде понял, только я сомневаюсь правильно или …   14.11.2004 10:37
Jahnerus   Флогримм: Помойму (я конечно могу ошибаться) но в…   14.11.2004 12:28
xds   Прямоугольник - частный случай четырехугольника, …   14.11.2004 15:38
Andy   Никак не могу найти верный алгоритм определения пр…   14.11.2004 22:57
volvo   Andy С английским проблемы есть? Если нет, то за…   14.11.2004 23:10
Andy   С таким английским проблемы есть :p2: Можете в о…   14.11.2004 23:18
volvo   Перевод: Далее описано простое решение проблемы ч…   14.11.2004 23:37
Флогримм   А можно другой алгоритм(хотя менее эффективный): с…   15.11.2004 10:01
Флогримм   program tri; uses crt; function len(a1,b1,a2,…   15.11.2004 12:00
volvo   Флогримм Я бы переписал функцию S по-другому... …   15.11.2004 13:45
Флогримм   ты прав! я когда уже от Нета отключился, тему…   15.11.2004 20:33
volvo   Флогримм Какую погрешность ты хочешь вычислить?   15.11.2004 20:58
Andy   Вот-вот, Флогримм. Я тоже хотел через площадь ре…   16.11.2004 1:08
volvo   Andy Вот здесь я нашел еще один алгоритм (правда,…   16.11.2004 2:08
Andy   Или алгоритм не работает, или я его не верно поним…   16.11.2004 3:07
Andy   Не воспринимает точку, которая лежит на линии (хот…   16.11.2004 3:26
volvo   Andy :( Да, у меня тоже начало глючить (причем в…   16.11.2004 3:34
Andy   Volvo В принципе алгоритм с лучом (тот, который т…   16.11.2004 3:49
volvo   Andy проверь РМ... ;) Добавлено Вот та функция…   16.11.2004 4:22
Andy   Да, пока работает. Но надо еще попроверять <_…   16.11.2004 16:17
volvo   Andy Я никогда не встречал, чтобы этот алгоритм …   16.11.2004 18:00
Andy   Да, я тоже не встречал. Мне его порекомендовали и …   16.11.2004 18:47
Флогримм   компьютер представляет число в виде десятичной д…   17.11.2004 11:37
Флогримм   когда создаешь тему или отправляешь сообщение на…   17.11.2004 11:40
volvo   Флогримм Можно уменьшить погрешность вычисления п…   17.11.2004 14:47
Guest   volvo, у меня есть решение к задаче, там написано …   18.11.2004 11:39
Andy   Кстати, все те кто решает через площадь! Вы на…   18.11.2004 22:54
volvo   Andy Заметь: «А», «Б», «В» - невыпуклые, т.е. н…   18.11.2004 23:04
Andy   А именно? Там должно, наверное, свойство выпуклост…   19.11.2004 0:53
volvo   Andy Смотри вот тут... По-моему, алгоритм должен …   19.11.2004 0:55
Andy   Спасибо, всем участникам. Я позавчера все-таки нап…   21.11.2004 1:09


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

 





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