Окружность и точки. Дельфи

[Rancid]

Доброго времени суток!! Собсно требуется решить такую задачу: определить радиус и центр такой окружности, проходящей хотя бы через три различные точки заданного множества точек на плоскости, что минимальна разность количеств точек, лежащих внутри и вне окружности. Помогите кто чем может не знаю как с этим справиться(( не знаю даже с чего начать

[maladoy]

www.programmersforum.ru/showthread.php?t=16960найти точку равноудаленную от этих 3-х это и будет центр потом найти растояние до этой точки и рисовать окружность!!!

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs;

type
  TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);
    procedure FormPaint(Sender: TObject);
    procedure FormMouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
    procedure FormMouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
  private
    P : array [1..3] of TPoint;
    CPoint : integer;
    Delta : TPoint;
    X0 : TPoint;
    R : integer;
    procedure ReCalcCircle;
  public
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
begin
   P[1].X := 100; P[1].Y := 100;
   P[2].X := 150; P[2].Y := 100;
   P[3].X := 125; P[3].Y := 200;
   ReCalcCircle;
end;

procedure TForm1.FormPaint(Sender: TObject);
begin
   if R > 0 then begin
      Canvas.Brush.Color := clBtnFace;
      Canvas.Pen.Color   := clBlue;
      Canvas.Ellipse(X0.X-R, X0.Y-R, X0.X+R, X0.Y+R);
   end;

   Canvas.Brush.Color := clGreen;
   Canvas.FillRect(rect(P[1].X-3, P[1].Y-3, P[1].X+3, P[1].Y+3));
   Canvas.FillRect(rect(P[2].X-3, P[2].Y-3, P[2].X+3, P[2].Y+3));
   Canvas.FillRect(rect(P[3].X-3, P[3].Y-3, P[3].X+3, P[3].Y+3));
end;

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
   if      (X >= P[1].X-5) and (Y >= P[1].Y-5) and (X <= P[1].X+5) and (Y <= P[1].Y+5) then CPoint := 1
   else if (X >= P[2].X-5) and (Y >= P[2].Y-5) and (X <= P[2].X+5) and (Y <= P[2].Y+5) then CPoint := 2
   else if (X >= P[3].X-5) and (Y >= P[3].Y-5) and (X <= P[3].X+5) and (Y <= P[3].Y+5) then CPoint := 3
   else CPoint := -1;
   Delta.Y := P[CPoint].X - X;
   Delta.Y := P[CPoint].Y - Y;
end;

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
   if CPoint = -1 then exit;
   P[CPoint].X := X + Delta.X;
   P[CPoint].Y := Y + Delta.Y;
   ReCalcCircle;
   refresh;
end;

procedure TForm1.FormMouseUp(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
   CPoint := -1;
end;

procedure TForm1.ReCalcCircle;
var A, B, x, y:double;
    k0, k1, k2, m0, m1, m2:double;
begin
   R := -1;
   k0 := sqr(P[1].X)-sqr(P[2].X) + sqr(P[1].Y)-sqr(P[2].Y);
   k1 := 2*(P[1].Y-P[2].Y);
   k2 := 2*(P[1].X-P[2].X);
   m0 := sqr(P[1].X)-sqr(P[3].X) + sqr(P[1].Y)-sqr(P[3].Y);
   m1 := 2*(P[1].Y-P[3].Y);
   m2 := 2*(P[1].X-P[3].X);
   A := (k2*m0 - k0*m2);
   B := (k2*m1 - k1*m2);
   if B = 0 then exit;
   y := A / B;
   X0.Y := trunc(y);
   if abs(m2) > 0.01 then x := (m0 - y * m1) / m2
   else
      if abs(k2) > 0.01 then x := (k0 - y * k1) / k2
      else exit;
   X0.X := trunc(x);

   R := trunc(sqrt(sqr(P[1].X-x) + sqr(P[1].Y-y)))
end;

end.

Координаты центра и радиус получается решением системы из трех уравнений

(x-a)^2 + (y-b)^2 = R^2 для трех точек

решение от Alexblack пользуйтесь поиском

[Rancid]

Спасибо! А как сравнить количество точек внутри окружности и вне ее?

[maladoy]

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

[Rancid]

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

[начинающий кодер]

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

[Spickard]

Сообщение от maladoy

procedure TForm1.ReCalcCircle;
var A, B, x, y:double;
    k0, k1, k2, m0, m1, m2:double;
begin
   R := -1;
   k0 := sqr(P[1].X)-sqr(P[2].X) + sqr(P[1].Y)-sqr(P[2].Y);
   k1 := 2*(P[1].Y-P[2].Y);
   k2 := 2*(P[1].X-P[2].X);
   m0 := sqr(P[1].X)-sqr(P[3].X) + sqr(P[1].Y)-sqr(P[3].Y);
   m1 := 2*(P[1].Y-P[3].Y);
   m2 := 2*(P[1].X-P[3].X);
   A := (k2*m0 - k0*m2);
   B := (k2*m1 - k1*m2);
   if B = 0 then exit;
   y := A / B;
   X0.Y := trunc(y);
   if abs(m2) > 0.01 then x := (m0 - y * m1) / m2
   else
      if abs(k2) > 0.01 then x := (k0 - y * k1) / k2
      else exit;
   X0.X := trunc(x);

   R := trunc(sqrt(sqr(P[1].X-x) + sqr(P[1].Y-y)))
end;

Не могли бы вы расписать как и откуда выводятся выделенные формулы? Желательно детальнее, подробнее. Ну и комментарии в коде не помешали бы.