Понадобицца:
Функция расстояния м-у точками
d(x1,y1,x2,y2)=sqrt((x1-x2)**2+(y1-y2)**2))

Функция полупериметра треугольника с длинами сторон a,b,c
p(a,b,c)=(a+b+c)/2

Функция площади треугольника с длинами сторон a,b,c
s(a,b,c)=
{
p=p(a,b,c);
s=sqrt(p*(p-a)*(p-b)*(p-c))
}

Фукция попадания точки x0,y0 в площадь треугольника (x1,y1,x2,y2,x3,y3)
find(x0,y0,x1,y1,x2,y2,x3,y3)
{
d1=d(x0,y0,x1,y1);
d2=d(x0,y0,x2,y2);
d3=d(x0,y0,x3,y3);

h12=d(x1,y1,x2,y2);
h13=d(x1,y1,x3,y3);
h23=d(x2,y2,x3,y3);

S0=s(h12,h13,h23);
S12=s(h12,d1,d2);
S13=s(h13,d1,d3);
S23=s(h23,d2,d3);

если S0=S12+S13+S23=> true точка входит
иначе false
}

если количество координат поселений больше 3
то проверять попадание для точек 1,2,3... затем 1,2,4... затем 1,2,5... итд до 1,2,N

Если хотя бы для одной проверки ф-я попдания в площадь треугольника вернет true - точка x0,y0 внутри поселения.

реф номер 132.
Денег (в тч игровых или прочих ресов и комплектующих) заказывать банально.
В отместку можешь подсобить временем, например, Атомными электростанциями уровня эдак 20 на моих колониях.
Думаю, красота оных сооружений будет достойной моих усилий...
ЗЫ. Крастоа решения в первую очередь зависит от четкости поставленной задачи..

Спасибо! Подумав, согласился, что из рамок лучше никого не выпускать. Пойду поднимать Атомную энергетику вручную...

Ну да... Недоработочка-с.. Извинияюсь.. На то и коллективный разум, дабы выискивать оные оплошности... Думаю, правильно зациклить по всем вариантам треугольников труда не составит. Долго - но надежно...
ЗЫ. Призовые, надеюсь, возвращать не придется мне... Потрачено уже почти все..

фукция нахождения коэффицента к от 2 точек

find_k(x1,y1,x2,y2):=
{
if x1==x2 then k=(y1-y2)*10000000
else к = (y1-y2)/(x1-x2)
}

организуем циклы

flag=false boolean;

for i=1 to n-2 do {
   for j=i+1 to n-1 {
      for k=j+1 to n {
         if (i!=j)&&(j!=k)&&(i!=k) then {  // проверка для 1 треугольника.   
//для первой вершины
           k1=find_k(x_i,y_i,x_j,y_j);   
           k2=find_k(x_i,y_i,x_k,y_k);
           k3=find_k(x_i,y_i,X,Y);   
             if k1<k2 then {max_K=k1; min_K=k2}
                          else {max_K=k2; min_K=k1};
             if (k1==k2==k3)or(max_k>=k3>=min_k) then {}// точка возможно принадлежит, продолжаем дальше
                                                                           else  {}// не принадлежит, продолжаем цикл , ушли из проверки этого треугольника

//для второй вершины
           k1=find_k(x_j,y_j,x_i,y_i);   
           k2=find_k(x_j,y_j,x_k,y_k);
           k3=find_k(x_j,y_j,X,Y);   
             if k1<k2 then {max_K=k1; min_K=k2}
                          else {max_K=k2; min_K=k1};
             if (k1==k2==k3)or(max_k>=k3>=min_k) then  {flag=true}// точка принадлежит треугольнику (заканчиваем все циклы)
                                                                           else  {}// не принадлежит треугольнику, идем в другой, продолжаем циклы
                        }}}}
если по итогом всех циклов flag даст значение true то точка принадлежит

Отредактировано vvv (2008-07-03 21:47:11)