ИНФОРМАТИКА ! НИД ХЕЛП!!11

[nDuD]

в общем задали проект на два месяца я его уже оформил тока задачу надо решить !

ХЕЛП ХЕЛП ХЕЛП  :pray:

 

В ПАСКАЛЕ ! :

 

Из заданного множества точек на плоскости выбрать 3 различные так, чтобы внутри треугольника содержалось максимальное количество точек этого множества.

 

если кто сможет с меня симпа!

[1010]

три самые крайние

[nDuD]

я рад но мне нужно решение  в паскале 

[Vermilion]

но только самые крайние бери

 

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

 

это то что пришло в голову первое, НО это стоооооооооолько переборов... если там точек не так уж много, то мб покатит=\

 

бляяяя все выше написанное для выпуклого множества... или конкретизируй задачу или простой огромный перебор

[nDuD]

чо конкретизировать она такая  и есть :о

 

[Vermilion]

ну множество может быть наперед сказано, что выпуклое, может быть там 1кккк точек и простой переор никак не поможет и будет работать 100 дней, пока даст ответ... закодить это вообще не проблема, думаю важен алгоритм...

[nDuD]

не знаю я не шарю в этом :О

но условие оно 100% такое

[4xan4]

суммон Сноб

[Yujin]

[adskii_troglotit]

  Цитата

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

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

[kveldulv]

находим центр системы, хз как, видимо надо просто все векторы перемножить.

 

от этого центра ищем крайние точки окружностями

 

ну вот и треугольник

 

скажи хоть специальность, потому что задача похожа на физическую, чтонить связанное с массами.

[adskii_troglotit]

^ неправ

[S[p]ake]

дщд

тут чо за хуевые программеры?

у тебя есть 2 точки (х,у), составляешь прямую, и ставишь условие, чтобы точки были под прямой!

[nDuD]

сразу говорю что я пас в паскале шарю на уровне ну совсем несложных задач потому и прошу решение в паскале а не идею решения =\

[T3h1D0L]

  Цитата

сразу говорю что я пас в паскале шарю на уровне ну совсем несложных задач потому и прошу решение в паскале а не идею решения =\

Как можно просить решение, если и идеи-то нет. Самая тупая, но точно верная идея это составить список всех возможных треугольников, а потом посмотреть в какой сколько точек попало. Для других решений нужно теоретическое обоснование которое с программированием не сильно связано, скорее с аналитической геометрией.

[nDuD]

  Цитата

  Цитата

сразу говорю что я пас в паскале шарю на уровне ну совсем несложных задач потому и прошу решение в паскале а не идею решения =\

Как можно просить решение, если и идеи-то нет. Самая тупая, но точно верная идея это составить список всех возможных треугольников, а потом посмотреть в какой сколько точек попало. Для других решений нужно теоретическое обоснование которое с программированием не сильно связано, скорее с аналитической геометрией.

ну я и прошу придумать как это решать и реализовать :(

 

[T3h1D0L]

Я в паскале не шарю, когда я учился, я сразу попросил препода разрешить мне писать на C/C++ ибо я его тогда уже знал, он был не против.

[bobriq]

я бы помог , но учусь в 8 классе 

[kveldulv]

Нашел на каком то сайте

паскаль офк не знаю, но там вроде все таки боле менее ясно, простой перебор без математики.

 

 

  Показать содержимое

Const

  LEFT = 1;

  RIGHT = 2;

  BEYOND = 3;

  BEHIND = 4;

  BETWEEN = 5;

  ORIGIN = 6;

  DESTINATION = 7;

 

Type

  TPoint = Record

    x : Real;

    y : Real;

  end;

 

  TVector = TPoint;

 

  TTriangle = Record

    A, B, C : TPoint;

  end;

 

Function VectorLength (v : TVector) : Real;

begin

  VectorLength := sqrt (sqr (v.x) + sqr (v.y));

end;

 

Function Classify (a : TPoint; b : TPoint; p : TPoint) : Byte;

var

  sa : Real;

  v1 : TVector;

  v2 : TVector;

 

begin

  v1.x := b.x - a.x;

  v1.y := b.y - a.y;

  v2.x := p.x - a.x;

  v2.y := p.y - a.y;

 

  sa := v1.x*v2.y - v1.y*v2.x;

 

  if sa > 0 then Classify := LEFT

  else if sa < 0 then Classify := RIGHT

  else if (v1.x*v2.x < 0) or (v1.y*v2*y < 0) then Classify := BEHIND

  else if (VectorLength (v1) < VectorLength (v2)) then Classify := BEYOND

  else if a = p then Classify := ORIGIN

  else if b = p then Classify := DESTINATION

  else Classify := BETWEEN;

end;

 

Function PointInTriangle (t : TTriangle; p : TPoint);

begin

  PointInTriangle := (Classify (t.A, t.B, p) <> LEFT) and (Classify (t.B, t.C, p) <> LEFT) and (Classify (t.C, t.A, p) <> LEFT);

end;

 

{ ============================== }

кусок программы

 

Const

  Nmax = 10000;

 

Type

  TPoints = array [1..Nmax] of TPoint;

 

Var

  p : TPoints;

  t : TTriangle;

  n : Word;  { кол-во реальных точек }

 

{ описание остальных переменных }

...

 

Begin

  { Инициализация, ввод данных }

  ...

  nMaxPoints := 0;

  { перебор всех троек точек }

  for i := 1 to n - 2 do

    for j := i + 1 to n - 1 do

      for k := j + 1 to n do

      begin

         t.A := p ;

         t.B := p [j];

         t.C := p [k];

 

         { проверяем все точки }

         nCount := 0;

         for m := 1 to n do

           if PointInTriangle (t, p [m]) then Inc (nCount);

 

         if nCount > nMaxPoints then begin

           nMaxPoints := nCount;

           maxTriangle := t;

         end;

  end;

 

  { Вывод результата }

  ...

End.

 

 

 

Там еще камент

 

  Показать содержимое

Ну и в чем проблема?

Определить, находится ли точка внутри треугольника, можно несколькими способами (везде треугольник будет обозначаться ABC, проверяемая точка - M):

 

1. Площадь треугольника ABC равна сумме площадей треугольников ABM, ACM и BCM. Решение строго математическое, но для компа, ИМХО, не годится, т.к. возможны проблемы с округлением. Простая формула для определения площади треугольника по координатам вершин выглядит так: S = 1/2 * [a, b], где a и b - вектора смежных сторон из общей точки, [a, b] - векторное произведение векторов a и b. Для треугольника ABC с координатами ((Xa, Ya), (Xb, Yb), (Xc, Yc)) площадь определяется так: S = 0.5 * ((Xb-Xa)*(Yc-Ya) - (Xc-Xa)*(Yb-Ya)).

 

2. Для точки M внутри треугольника ABC сумма углов при вершине M треугольников ABM, ACM и BCM равна 360 градусов (2*пи). Косинус угла определяется как скалярное произведение векторов, исходящих из этой точки, разделенное на произведение длин этих векторов. Способ не очень хороший, т.к. помимо округлений требует большого количества вычислений.

 

3. Функция Classify в приложении определяет положение заданной точки относительно заданного отрезка (вектора). Вектор разделяет плоскость на 7 непересекающихся областей (см. http://www.kamlit.ru/docs/aloritms/algolist.manual.ru/maths/geom/datastruct.php.htm), и данная функция сообщает, какой из этих областей принадлежит точка.

Функция основана на свойствах векторного произведения векторов.

 

Используя данную функцию можно определить принадлежность точки треугольнику с помощью 3-х проверок (см. функцию PointInTriangle в приложении).

 

 

  Показать содержимое

 

 

Класс вроде целиком приведен, если вдруг не заработает, то этот класс автор явно спиздил с сайта algolist.ru, там он есть целиком

 

[nDuD]

это че воще  :palevo:  

думаю мне бы такое не задали + в паскале мне выдает ошибку : операнды имеют неприводимые типы

 

я так понимаю там ввести их надо ... но я даже боюсь в этом разбираться