Множество точек и круг

Всем привет... Парни помогите с понятием формулировки:на плоскости заданно множество точек М и круг. Выбрать из М две различные точки так, чтобы наименьшим образом различались количество точек в круге, лежащие по разные стороны от прямой, проходящей через эти точки.Заранее Спасибо...Вроде формулировку понял, т.е надо начертить так круг и провести прямую чтобы в обеих сторонах было наименьшим образом различалось количество точек в круге.А теперь такой вопрос, подскажите Алгоритм по пунктам???Я так понимаю: 1. рисуем круг который охватывает все точки 2. и начинаем перебор построения прямых так чтобы с одно и другой стороны было равное кол-во точек НО тогда суть окружности!!! зачем она нужна!!! и без нее же все можно сделать...
11 ответов

найти две точки, провести через них прямую, которая разделит круг на 2 части. найти такие точки, чтобы в двух частях круга было равное(наиболее близкое) количество точек из M


Biggemot, а круг по какому принципу рисовать???А еще будут варианты???


1. рисуем круг который охватывает все точки 2. и начинаем перебор построения прямых так чтобы с одно и другой стороны было равное кол-во точек НО тогда суть окружности!!! зачем она нужна!!! и без нее же все можно сделать...
п.1 надо отменить - тогда окружность будет нужна. - Т. е., в задании: дано множество точек и круг. Это не означает, что все точки попадают внуть круга. Какие-то скорее всего не попадут. Хотя может быть что и все точки попадут внутрь круга - это лишь частный случай. Алгоритм надо строить именно из предположения, что не все точки могут быть внутри круга. Т. е. алгоритм такой: 1. Ищем точки, которые попадют внутрь круга. - Это точки расстнояние до которых от центра круга меньше или равно радиусу круга. 2. На множестве этих точек перебираем все варианты прямых и одновременно вычисяем разности между кол-вом точек с разных сторон. В этом же цикле ищем минимум этой разности и запоминаем пару точек, соответствующих этому минимуму.


Mawrat, Спасибо, я это уже понял....... Но, а каким обзором рисуется круг, какой радиус, где его центр??? Я так понимаю тут будет еще один перебор на центр и радиус окружности ,а потом уже п1 и п2 ....


По условию задачи - множество точек и круг уже заданы. Т. е. нужно сформировать начальные условия. Например, так:
procedure TForm1.Button1Click(Sender: TObject);
type
  //Круг.
  TCircle = record
    Center : TPoint;
    Radius : Integer;
  end;
const
  //Количество точек.
  N = 30;
var
  //Массив точек.
  Arr : array[1..N] of TPoint;
  //Круг.
  Circle : TCircle;
  //Индекс для циклов.
  i : Integer;
begin
  //Формирование начальных условий.
 
  //Массив точек.
  Randomize;
  for i := Low(Arr) to High(Arr) do begin
    Arr[i].X := Random(401);
    Arr[i].Y := Random(401);
  end;
 
  //Круг.
  Circle.Center.X :=  150 + Random(101);
  Circle.Center.Y :=  150 + Random(101);
  Circle.Radius := 100 + Random(51);
  
  //Начальные условия сформированы.
 
  //Решение задачи.
  ...
end;
Т. е. мы формируем массив точек, координаты которых не выходят за пределы квадрата 0..400. Затем выбираем параметры круга - так чтобы его центр оказался где-то в центральной зоне квадрата (квадрат у нас - 0..400). И радиус круга выбираем так, чтобы получившийся круг не вышел за пределы квадрата.


конечно если поможет тебе это дело...)))в архиве 3 проги... поэтому типу написаны.. глянь мож чё найдёшь)))


Mawrat, Спасибо в общем буду отталкиваться от случайных чисел...А вот такой еще вопрос, прямая же должна разделить окружность от одной точки до другой (отрезок) или же прямая просто строиться по двум точкам и делит круг...!!!


Прямая строится по двум точкам - т. е. это бесконечная линия, которая проходит через 2 точки. Я завтра отпишу сюда, что и как надо делать - по шагам.


Укрупнённый план. 1. Составить массив из случайных точек. 2. Задать параметры круга - случайная точка (центр круга) + случайный радиус. 3. Найти все точки, которые попадают внутрь круга. 4. Спроектировать цикл, перебирающий все пары точек (по этим парам строятся линии). 5. Внутри этого цикла подсчитывается баланс - разность между количеством точек, оказавшихся по одну строну от линии и количеством точек - по другую сторону линии. Одновременно ищется минимальный баланс (минимальная разность по абсолютной величине). Запоминаем, также, координаты линии при этом минимальном балансе. --- Основные операции которые требуется выполнять. (Ссылки на теорию нашёл в одном из постов уважаемого Puporev-а ) 1. Вычисление уравнения прямой: KA * x + KB * y + KC = 0. - Т. е. вычисление коэффициентов KA, KB, KC этого уравнения. Теория. 2. Определение: лежит ли точка на заданной прямой. Теория. 3. Определение полуплоскости, в которой лежит точка. Теория. --- Вариант решения:
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls;
 
type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Image1: TImage;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 
  //Класс, представляющий отрезок или прямую AB.
  TLine = class(TObject)
  private
    //Точки отрезка.
    FDotA : TPoint;
    FDotB : TPoint;
    //Коэффициенты уравнения прямой. FKA * x + FKB * y + FKC = 0.
    FKA, FKB, FKC : ******;
    //Точность в операциях сравнения вещественных чисел.
    FEpsilon : ******;
    //Расчёт коэффициентов уравнения прямой.
    procedure CalcEquation;
    //Задать точку А.
    procedure SetDotA(const aDotA : TPoint);
    //Задать точку Б.
    procedure SetDotB(const aDotB : TPoint);
  public
    //Конструктор.
    constructor Create; overload;
    //Конструктор с параметрами.
    constructor Create(const aDotA, aDotB : TPoint; const ******** : ******); overload;
    //Доступ к сведениям о точности.
    property Epsilon : ****** read FEpsilon write FEpsilon;
    //Задать точки А и Б.
    procedure SetDotAB(const aDotA, aDotB : TPoint);
    //Доступ к точке А.
    property DotA : TPoint read FDotA write SetDotA;
    //Доступ к точке Б.
    property DotB : TPoint read FDotB write SetDotB;
    //Лежит ли точка на прямой.
    function IsOnLine(const aDot : TPoint) : Boolean;
    //Расположены ли точки 1 и 2 в одной и той же полуплоскости относительно прямой АБ.
    function IsOnSide(const aDot1, aDot2 : TPoint) : Boolean;
  end;
 
  //Круг.
  TCircle = record
    Center : TPoint;
    Radius : Integer;
  end;
 
  //Массив точек.
  TArrDot = array of TPoint;
 
const
  //Величина приращения длины динамического массива.
  Capacity = 10;
  //Точность сравнения вещественных чисел.
  Epsilon = 0.01;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.dfm}
 
uses Math, Types;
 
//******************************************************************************
//Реализация класса TLine. Начало.
//******************************************************************************
 
constructor TLine.Create;
begin
  inherited Create;
  FDotA.X := 0;
  FDotA.Y := 0;
  FDotB.X := 0;
  FDotB.Y := 0;
  FKA := 0;
  FKB := 0;
  FKC := 0;
  FEpsilon := 0.01;
end;
 
constructor TLine.Create(const aDotA, aDotB: TPoint; const ********: ******);
begin
  inherited Create;
  FDotA := aDotA;
  FDotB := aDotB;
  FEpsilon := ********;
  CalcEquation;
end;
 
procedure TLine.CalcEquation;
begin
  FKA := FDotA.Y - FDotB.Y;
  FKB := FDotB.X - FDotA.X;
  FKC := FDotA.X * FDotB.Y - FDotB.X * FDotA.Y;
end;
 
procedure TLine.SetDotAB(const aDotA, aDotB: TPoint);
begin
  FDotA := aDotA;
  FDotB := aDotB;
  CalcEquation;
end;
 
procedure TLine.SetDotA(const aDotA: TPoint);
begin
  FDotA := aDotA;
  CalcEquation;
end;
 
procedure TLine.SetDotB(const aDotB: TPoint);
begin
  FDotB := aDotB;
  CalcEquation;
end;
 
function TLine.IsOnLine(const aDot: TPoint): Boolean;
begin
  if (FKA = 0) and (FKB = 0) then begin
    raise Exception.Create('Ошибка. Линия не инициализирована.');
  end;
  Result := SameValue( FKA * aDot.X + FKB * aDot.Y + FKC, 0, FEpsilon );
end;
 
function TLine.IsOnSide(const aDot1, aDot2: TPoint): Boolean;
begin
  if (FKA = 0) and (FKB = 0) then begin
    raise Exception.Create('Ошибка. Линия не инициализирована.');
  end;
  Result := ( FKA * aDot1.X + FKB * aDot1.Y + FKC ) * ( FKA * aDot2.X + FKB * aDot2.Y + FKC ) > 0
end;
 
//Реализация класса TLine. Конец.
 
//Рисование на канве.
 
//Очистка канвы компонента TImage.
procedure ClearCanvas(aImage : TImage);
begin
  with aImage do begin
    Canvas.FillRect( Rect(0, 0, Width, Height) );
  end;
end;
 
//Прописовка точки.
procedure DrawDot(aCanvas : TCanvas; const aDot : TPoint);
begin
  //Рисуем вокруг точки квадрат с заливкой.
  aCanvas.Rectangle(
    aDot.X - 1, aDot.Y - 1,
    aDot.X + 1, aDot.Y + 1
  );
end;
 
//Прорисовка окружности.
procedure DrawCircle(const aCanvas : TCanvas; const aCircle : TCircle);
begin
  with aCanvas, aCircle do begin
    Arc(
      Center.X - Radius, Center.Y - Radius, Center.X + Radius, Center.Y + Radius,
      Center.X + Radius, Center.Y + Radius, Center.X - Radius, Center.Y - Radius
    );
    Arc(
      Center.X + Radius, Center.Y + Radius, Center.X - Radius, Center.Y - Radius,
      Center.X - Radius, Center.Y - Radius, Center.X + Radius, Center.Y + Radius
    );
  end;
end;
 
//Прорисовка линии.
procedure DrawLine(const aCanvas : TCanvas; const aDotA, aDotB : TPoint);
begin
  aCanvas.MoveTo(aDotA.X, aDotA.Y);
  aCanvas.LineTo(aDotB.X, aDotB.Y);
end;
 
//Вычисление расстояния между точками 1 и 2.
function Distance(const aDot1, aDot2 : TPoint) : ******;
begin
  Result := Sqrt( Sqr(aDot2.X - aDot1.X) + Sqr(aDot2.Y - aDot1.Y) );
end;
 
procedure TForm1.Button1Click(Sender: TObject);
const
  //Количество точек.
  N = 30;
var
  //Исходный массив точек.
  ArrDotDef : TArrDot;
  //Массив точек, которые расположены в пределах круга.
  ArrDot : TArrDot;
  //Индексы искомых точек.
  IndDotA, IndDotB : Integer;
  //Круг.
  Circle : TCircle;
  //Линия.
  Line : TLine;
  //Индексы для циклов.
  i, j, k, s : Integer;
  //Баланс. - Счётчики разности.
  DiffCount, DiffCountMin : Integer;
  //Строка для алгоритма распечатки.
  StrTmp : String;
begin
  //Формирование начальных условий.
 
  //Исходный массив точек.
 
  //Выделяем память для массива.
  SetLength(ArrDotDef, N);
 
  Randomize;
  for i := Low(ArrDotDef) to High(ArrDotDef) do begin
    ArrDotDef[i].X := Random(401);
    ArrDotDef[i].Y := Random(401);
  end;
 
  //Круг.
  Circle.Center.X :=  150 + Random(101);
  Circle.Center.Y :=  150 + Random(101);
  Circle.Radius := 100 + Random(51);
 
  //Начальные условия сформированы.
 
  //Решение задачи.
 
  //Составляем массив из точек, которые лежат в пределах круга.
  j := 0;
  for i := 0 to High(ArrDotDef) do begin
    //Если расстояние от точки до центра круга не превышает радиуса круга,
    //тогда добавляем эту точку в массив ArrDot.
    if Distance(Circle.Center, ArrDotDef[i]) <= Circle.Radius then begin
      //Если требуется, увеличиваем длину массива ArrDot.
      if j = Length(ArrDot) then begin
        SetLength(ArrDot, Length(ArrDot) + Capacity);
      end;
      //Добавляем точку в массив ArrDot.
      ArrDot[j] := ArrDotDef[i];
      //Индекс следующего элемента массива.
      Inc(j);
    end;
  end;
 
  //Корректируем длину массива в соответствии с количеством добавленных
  //в него элементов.
  if Length(ArrDot) > j then begin
    SetLength(ArrDot, j);
  end;
 
  //Создаём объект "Линия".
  Line := TLine.Create;
  //Задаём точность.
  Line.Epsilon := Epsilon;
 
  //Запускаем цикл перебора пар точек.
  //Флаг в состоянии: "Ни одна пара точек не найдена".
  IndDotA := -1;
  for i := 0 to High(ArrDot) - 1 do begin
    for j := i + 1 to High(ArrDot) do begin
 
      //Если точки совпадают - пропускаем итерацию.
      if ( ArrDot[i].X = ArrDot[j].X ) and ( ArrDot[i].Y = ArrDot[j].Y ) then Continue;
 
      //Инициализируем линию.
      Line.SetDotAB(ArrDot[i], ArrDot[j]);
 
      //Выбираем индекс первой точки, которая не лежит на прямой.
      for k := 0 to High(ArrDot) do begin
        if not Line.IsOnLine(ArrDot[k]) then Break;
      end;
 
      if k = Length(ArrDot) then begin
        //Это означает, что все точки лежат на одной прямой.
        //В этом случае продолжать выполнение нет смысла.
        //Если такой файкт имеет место, то обнаружится он уже на первой итерации.
        ShowMessage('Все точки лежат на одной прямой. Действие отменено.');
        //Удаляем объект-линию из памяти.
        Line.Free;
        //Выходим из процедуры.
        Exit;
      end;
 
      //Точка, не лежашая на прямой, найдена. Индекс этой точки = k.
      //В дальнейшем точки будем называть по их индексам. Т. е. только что найденную точку
      //назовём точкой К.
 
      //Итак, мы имеем линию, которая в данный момент представлена объектом Line.
      //Эта линия делит плоскость на две полуплоскости.
      //Могут быть точки, лежащие на прямой Line - их мы не будем учитывать, так как они
      //не влияют на баланс.
      //Будем считать, что точка, которая лежит в той же полуплоскости, что и точка К,
      //учитывается в балансе со значением (+1), т. е.: Inc(DiffCount).
      //Если же некоторая точка и точка К лежат в разных полуплоскостях -
      //такая точка учитывается в балансе со значением (-1), т. е.: Dec(DiffCount).
      //Таким образом, чем меньшая получится величина Abs(DiffCount) тем большее равновесие
      //соответствует данной линии.
 
      //Итак, одну точку, не лежащую на прямой, мы уже нашли - это точка К.
      //Подсчитываем эту точку в балансе.
      DiffCount := 1;
 
      //Подсчёт баланса по остальным точкам.
      for s := k + 1 to High(ArrDot) do begin
        //Если очередная точка лежит на прямой - пропускаем её.
        if Line.IsOnLine(ArrDot[s]) then Continue;
        //Учитываем очередную точку в балансе.
        if Line.IsOnSide(ArrDot[k], ArrDot[s]) then begin
          //Очередная точка расположена в той же полуплоскости, что и точка К.
          Inc(DiffCount);
        end else begin
          //Очередная точка и точка К расположены в разных полуплоскостях.
          Dec(DiffCount);
        end;
      end;
 
      //В первой итерации инициализируем параметры минимума.
      if IndDotA = -1 then begin
        //Текущее значение минимального баланса.
        DiffCountMin := DiffCount;
        //Текущие индексы точек, соответствующих минимальному балансу.
        IndDotA := i;
        IndDotB := j;
      end;
 
      //Уточняем сведения о минимуме.
      if Abs(DiffCount) < Abs(DiffCountMin) then begin
        //Баланс.
        DiffCountMin := DiffCount;
        //Индексы точек, которые соответствуют этому балансу.
        IndDotA := i;
        IndDotB := j;
      end;
    end;
  end;
 
  //Удаляем объект-линию из памяти.
  Line.Free;
 
  //Блок распечатки.
 
  //Очищаем Мемо.
  Memo1.Clear;
 
  //Распечатываем исходный массив точек.
  Memo1.Lines.Add('Исходный массив точек:');
  StrTmp := '';
  for i := 0 to High(ArrDotDef) do begin
    //В каждой строке распечатываем не более 10 элементов.
    if (i > 0) and (i mod 10 = 0) then begin
      Memo1.Lines.Add(StrTmp);
      StrTmp := ''
    end;
    if StrTmp <> '' then StrTmp := StrTmp + '; ';
    StrTmp :=
      StrTmp + '(' + IntToStr(ArrDotDef[i].X)
      + ', ' + IntToStr(ArrDotDef[i].Y) + ')';
  end;
  Memo1.Lines.Add(StrTmp);
 
  //Распечатываем массив точек, которые расположены в пределах круга.
  Memo1.Lines.Add('Массив точек, которые расположены в пределах круга:');
  StrTmp := '';
  for i := 0 to High(ArrDot) do begin
    //В каждой строке распечатываем не более 10 элементов.
    if (i > 0) and (i mod 10 = 0) then begin
      Memo1.Lines.Add(StrTmp);
      StrTmp := ''
    end;
    if StrTmp <> '' then StrTmp := StrTmp + '; ';
    StrTmp :=
      StrTmp + '(' + IntToStr(ArrDot[i].X)
      + ', ' + IntToStr(ArrDot[i].Y) + ')';
  end;
  Memo1.Lines.Add(StrTmp);
 
  //Показываем результат исследования.
  Memo1.Lines.Add('Заданное множество точек наиболее сбалансировано относительно линии:');
  Memo1.Lines.Add(
    '(' + IntToStr(ArrDot[IndDotA].X) + ', ' + IntToStr(ArrDot[IndDotA].Y) + ')'
    + ', (' + IntToStr(ArrDot[IndDotB].X) + ', ' + IntToStr(ArrDot[IndDotB].Y) + ')'
  );
  Memo1.Lines.Add('Баланс = ' + IntToStr(DiffCountMin));
 
  //Блок прорисовки.
 
  //Очищаем канву.
  //Цвет кисти - белый.
  Image1.Canvas.Brush.Color := RGB(255, 255, 255);
  ClearCanvas(Image1);
 
  //Рисуем все точки исходного массива.
  //Цвет пера - синий.
  Image1.Canvas.Pen.Color := RGB(0, 0, 255);
  for i := 0 to High(ArrDotDef) do begin
    DrawDot(Image1.Canvas, ArrDotDef[i]);
  end;
 
  //Рисуем круг.
  //Цвет пера - зелёный.
  Image1.Canvas.Pen.Color := RGB(0, 255, 0);
  DrawCircle(Image1.Canvas, Circle);
 
  //Рисуем найденную линию.
  //Цвет пера - красный.
  Image1.Canvas.Pen.Color := RGB(255, 0, 0);
  DrawLine(Image1.Canvas, ArrDot[IndDotA], ArrDot[IndDotB]);
 
end;
 
end.
Здесь я спроектировал класс, который представляет линию (прямую). Перечисленные выше операции реализованы в виде методов этого класса. Если, нужно - класс можно убать, а операции оформить в виде "свободных" процедур. Но с классом удобнее, я считаю. --- Если задачу погонять, можно заметить, что во всех случаях баланс равен 1 или 0 или -1. Это естественно - если в круг попало чётное количество точек, то баланс будет скорее всего равен нулю. Если количество точек нечётное - в этом случае баланс равен 1 или -1. "Скорее всего" - это потому что может быть ситуация, когда на одной прямой окажется более 2 точек, либо одна из точек по координатам совпадёт с другой - в этом случае при чётном количестве точек внутри круга можно получить баланс 1 или -1. И обратно - при нечётном количестве - может получиться баланс = 0. Правда если точки выбираются случайным образом, то вероятноть этого очень мала. Такую ситуацию можно смоделировать, если задавать точки вручную.


Опечатался - по п.п. 1 и 2 - Теория. По п.3: Теория.


Mawrat, Огромное спасибо!!! За задачу и за теорию где все рассказано и показано...