Версия для печати темы

Автор: Rudolf 27.10.2006 20:21

Задача такая: Из заданного на плоскости множества точек выбрать 3, не лежащих на одной прямой и состовляющих треугольник наименьшей площади.
Как я понимаю плоскость задаем в виде двумерного массива?А что с этим массивом потом делать?

Автор: Michael_Rybak 27.10.2006 20:54

Плоскость нет (по-моему) смысла задавать двумерным массивом. Задавать нужно *точки*, а не плоскость. Точки можно задать (одномерным) массивом, каждый элемент - пара (x, y). Или двумя массивами - x[1..n] и y[1..n].

Лобовое решение - тремя вложенными циклами перебрать первую, вторую и третью точки, и выбрать наилучший треугольник. Это будет O(n^3).

Решение похитрее - за O(n^2). Расскажу, если кому-то действительно интересно.

Может можно и за O(n log n). Но это уже совсем сложно, надо думать.

Автор: мисс_граффити 27.10.2006 22:06

если границы цикла грамотно установить - оценка чуть получше будет... то есть каждое сочетание проверить один раз. Ведь треугольники из точек с номерами 1,2 и 3 (123, 132, 213, 231, 321, 312) имеют одну и ту же площадь.

Автор: Michael_Rybak 27.10.2006 22:11

Это не меняет асимптотики.

Автор: мисс_граффити 28.10.2006 0:16

я не спорю.
просто дополнила.

Автор: Rudolf 28.10.2006 19:21

Вот что смог написать, только ничего не работает

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
int main(void)
  { clrscr();
     int X[10],Y[10],i,j,k;
     float s,Smin,a,b,c,p;
     for (i=0;i<=9;i++)
     { 
        X[i]=random(100);
        Y[i]=random(100);
      }

      for (i=0;i<=9;i++)
     { 
          a=abs(X[i]-Y[i]);
          for (j=1;j<=9;j++)
          {  
             b=abs(X[j]-Y[j]);
  
             for (k=2;k<=9;k++)
            {
               c=abs(X[k]-Y[k]);
               p=(a+b+c)/2;
               s=sqrt(p*(p-a)*(p-b)*(p-c));
               if (i==0) Smin=s;
               else if (s<Smin) Smin=s;
             }
           }
        }
      cout<<"Smin="<<Smin;
      getch();
      return 0;
  }

Автор: мисс_граффити 28.10.2006 20:37

так... площадь ты пытаешься считать по формуле Герона - логично.
только а,b и c как-то странно находишь
длина стороны - это расстояние между двумя точками, а не разность между двумя координатами одной точки...

Автор: Rudolf 28.10.2006 20:55

Ой!!Точно!Я чего то ступил))

Автор: Rudolf 28.10.2006 21:38

А формула для длины отрезка такая sqrt[ (x1-x2)^2 + (y1-y2)^2 ]?Я переделал но все равно ничего не работает

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
int main(void)
  { clrscr();
     int X[10],Y[10],i,j,k;
     float s,Smin,a,b,c,p;
     for (i=0;i<=9;i++)
     { 
        X[i]=random(100);
        Y[i]=random(100);
      }

      for (i=0;i<=9;i++)
     { 
          a=sqrt((X[i+1]-X[i])*(X[i+1]-X[i])+(Y[i+1]-Y[i])*(Y[i+1]-Y[i]);
          for (j=1;j<=9;j++)
          {  
             b=sqrt((X[j+1]-X[j])*(X[j+1]-X[j])+(Y[j+1]-Y[j])*(Y[j+1]-Y[j]);
  
             for (k=2;k<=9;k++)
            {
               c=sqrt((X[k+1]-X[k])*(X[k+1]-X[k])+(Y[k+1]-Y[k])*(Y[k+1]-Y[k]);
               p=(a+b+c)/2;
               s=sqrt(p*(p-a)*(p-b)*(p-c));
               if (i==0) Smin=s;
               else if (s<Smin) Smin=s;
             }
           }
        }
      cout<<"Smin="<<Smin;
      getch();
      return 0;
  }

Автор: volvo 28.10.2006 21:46

попробуй вот так:

#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <values.h>

#define SQR(x) (x)*(x)

int main(void) {

     clrscr();
     int X[10],Y[10],i,j,k, min_1, min_2, min_3;
     float Smin = MAXINT,a,b,c,p;
     for (i=0;i<=9;i++) {
        X[i]=random(100);
        Y[i]=random(100);
        cout << "(" << X[i] << ";" << Y[i] << ") ";
     }

     for (i=0;i<=9;i++) {
          for (j=1;j<=9;j++) {

             b=sqrt(SQR(X[j] - X[i]) + SQR(Y[j] - Y[i]));

             for (k=2;k<=9;k++) {

               c=sqrt(SQR(X[k] - X[j]) + SQR(Y[k] - Y[j]));
               a=sqrt(SQR(X[k] - X[i]) + SQR(Y[k] - Y[i]));

               if(a+b==c || a+c==b || b+c==a) continue;

               p = (a+b+c)/2;
               float s = sqrt(p*(p-a)*(p-b)*(p-c));

               if(s < Smin) {
                   Smin = s;
                   min_1 = i, min_2 = j, min_3 = k;
               }
             }
          }
     }
     cout << endl << "Smin = " << Smin << endl;
     cout << "pnt 1: " << min_1 << " " << endl
          << "pnt 2: " << min_2 << " " << endl
          << "pnt 3: " << min_3 << endl;
     getch();
     return 0;
}

Автор: Rudolf 28.10.2006 21:56

Все работает. Всем большое спасибо за помощь

Автор: Michael_Rybak 28.10.2006 23:19

Площадь, ИМО, лучше все-таки считать векторным произведением:

2s = (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)