Работа с массивами.

[inc]

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


как это сделать подскажите пожалуйста

[Serge_Bliznykov]

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

при этом учтите, что точки первого множества могут находится внутри условного многоугольника, образованного точками второго. В этом случае задача НЕ ИМЕЕТ решения - т.к. нельзя покрыть точки второго, если они за пределами точек первого. Этот вариант надо предусмотреть и выдать соответствующее сообщение.

ну и последнее. Обычно принято указывать язык программирования, на котором Вы решаете задачу, и указывать свои наработки.
Ну, хотя бы ввод координат множеств в вашем случае...

[inc]

спасибо что ответили мне просто сложно в этом разобраться

язык программирования C++

вот мой код но он очень кривой и не подходит для это решения задачи ,если кто сможет помогите пожалуйста написать эту программу

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <fstream>

using namespace std;
struct Point
{
    float x;
    float y;
};
#define N 5
Point points[N];
int TestTriangle(Point A,Point B, Point C);
int main()
{

  fstream fIn ("points.txt", ios::in);
  if (fIn.fail ())   return 1;

  char line[100];
  int k=0;

  for(int i=0;i<N;i++)
  {

    fIn.getline(line, 100,' ');
    k=strlen(line);
    line[k]=0;
    points[i].x = atof(line);

    fIn.getline(line, 100,'\n');
    k=strlen(line);
    line[k]=0;
    points[i].y = atof(line);
  }

   // Минимальная разность и координаты треугольника
   Point minA,minB,minC;
   int min=N;
   // Текущая разность
   int cur;

   for(int i=0;i<N-2;i++)   // Цикл для первой вершины
   {
    for(int j=i+1;j<N;j++)    // Цикл для второй вершины(не включает точки просмотренные для первой)
    {
     for(int k=j+1;k<N;k++)   // Цикл для третей вершины(не включает точки просмотренные для первой и второй)
     {
      cur = TestTriangle(points[i],points[j],points[k]);
      if(cur<min)
      {
          minA=points[i];
          minB=points[j];
          minC=points[k];
          min=cur;
      }
     }
    }
   }
 cout<<"Triangle: "<<endl;
 cout<<minA.x<<"\t"<<minA.y<<endl;
 cout<<minB.x<<"\t"<<minB.y<<endl;
 cout<<minC.x<<"\t"<<minC.y<<endl;
 cout<<"sub = "<<min;
 cin>>min;
 fIn.close();
 return 0;
}


int TestTriangle(Point A,Point B, Point C)
{
 Point T;
 int s1,s2,s3;
 int internal=0;
 int external=0;
 for(int i=0;i<N;i++)             // Цикл проверки всех точек
 {
  T=points[i];
  if(memcmp(&A,&T,sizeof(Point))==0||memcmp(&B,&T,sizeof(Point))==0||memcmp(&C,&T,sizeof(Point))==0)            // Исключаем текущие вершины треугольника
    continue;

  s1=(B.x-A.x)*(T.y-A.y)-(B.y-A.y)*(T.x-A.x);
  s2=(C.x-B.x)*(T.y-B.y)-(C.y-B.y)*(T.x-B.x);
  s3=(A.x-C.x)*(T.y-C.y)-(A.y-C.y)*(T.x-C.x);

  if(s1*s2*s3>0)        // Если точка вне треугольника
    external++;
  else
    internal++;
 }
 return external-internal;
}

заранее большое спасибо