Помогите по графике пожалуйста

[surovii]

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

может кто знает как это дело можно оформить..

ну или хотя бы помогите понять задание..

[Sazary]

Как я понял:
Дано множество кругов. Они, видимо, заданы координатами центров и радиусами.
Есть множество точек T (одна точка имеет координаты x и y).
Нужно найти такие 3 точки, для которых, если построить треугольник, количество кругов, в которые входит этот треугольник будет меньше всего отличаться от количества кругов, которые входят в него.

[surovii]

спасибо конечно, но как это более точно себе представить?

[Sazary]

Смотрите на рисунок. Есть несколько кругов.
И есть множество точек. Скажем, их 6.
Возьмем первые три точки и построим треугольник (на рис - Т1). Возьмем следующие 3 точки и построим второй треугольник (Т2).

Внутри треугольника Т1 находятся 2 круга. Также сам Т1 находится внутри двух кругов. То есть разность = 0.

Внутри треугольника Т2 один круг. И сам Т2 не находится внутри какого-либо круга. Разность = 1.

Значит, искомые точки - вершины треугольника Т1.

Я рассмотрел только 2 треугольника, но их будет больше (все комбинации из 6 точек).

-------------
Имхо, самое сложное здесь - функция, проверяющая находится ли внутри треугольника окружность.

Проверить, лежит ли треугольник внутри круга легко - просто убедиться, что все его вершины внутри круга.

--------------
Некоторые мысли:
чтобы проверить, лежит ли круг внутри треугольника, нужно найти длину перпендикуляра из центра соответствующего круга к стороне треугольника (всего их три). Если радиус <= перпендикуляр (и так для каждого), то круг внутри треугольника.

[surovii]

понятненько)) значит я точно влип..
ладно спасибо за наглядность..
математический модуль тут будет приличный гхм..
напрашивается вопрос: с чего начинать?

[Sazary]

напрашивается вопрос: с чего начинать?

Здесь упор на математику. Написать на ЯП будет несложно.

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

[surovii]

хм..спасибо..
если будут какие-нибудь новости или дополнения то буду очень благодарен..
а по ходу действия я ещё наверное буду задавать вопросы

вот нахождение прямой по двум тьочкам я знаю но как его применить?

[Sazary]

surovii
Дальше ищете уравнение прямой, перпендикулярной ей. Затем ищете точку пересечения. И находите длину отрезка.
Я сейчас как раз вывожу конечное уравнение для точек отрезка.
Попробуйте и вы.

[surovii]

да..вот ещё.. хотел бы спросить что выполняет данная прогрмма

type
error=Record
x:real;
y:real;
end;
mas=array [1..100] of error;

var
  Form1: TForm1;

T:array [1..100] of error;
R:real;
num:array[1..3] of integer;

implementation


{$R *.dfm}
uses Unit2,Unit3;

type comptype=record
g,h,j:real;
end;
var comp: comptype;
f,f1: file of comptype;

procedure u(x1,x2:error;var A,B,C:real);
begin
A:=x1.y-x2.y;
B:=x2.x-x1.x;
C:=x1.x*x2.y-x2.x*x1.y;
end;

function l(x,y:error):real;
begin
result:=sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));
end;

function r1(T:error;A,B,C:real):real;
begin
result:=(A*T.x + B*T.y + C)/sqrt(sqr(A)+sqr(B));
end;

function s(A,B,C:error):real;
begin
result:=abs(0.5*(A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y));
end;

function t1(T:error;A,B,C:error):boolean;
begin
if abs(s(A,B,T)+s(B,C,T)+s(A,C,T)-s(A,B,C))<0.01
then result:=true
else result:=false;
end;

procedure p(A,B,C:real;D:error; var A2,B2,C2:real);
begin
A2:=B;
B2:=(-1)*A;
C2:=A*D.y-B*D.x;
end;

function e(x1,x2:error; T:error; R:real):boolean;
var A,B,C:real;
A2,B2,C2:real;
begin
result:=false;
if (sqrt(sqr(x1.x-T.x)+sqr(x1.y-T.y))<R)
and (sqrt(sqr(x2.x-T.x)+sqr(x2.y-T.y))>R) then result:=true;
if (sqrt(sqr(x2.x-T.x)+sqr(x2.y-T.y))<R)
and (sqrt(sqr(x1.x-T.x)+sqr(x1.y-T.y))>R) then result:=true;

u(x1,x2,A,B,C);
p(A,B,C,T,A2,B2,C2);
if (sqrt(sqr(x2.x-T.x)+sqr(x2.y-T.y))>R)
and (sqrt(sqr(x1.x-T.x)+sqr(x1.y-T.y))>R)
then
if abs(r1(T,A,B,C))<R then
if r1(x1,A2,B2,C2)*r1(x2,A2,B2,C2)<0
then result:=true;
end;

function k1(T:error;R:real;X,Y,Z:error):real;
begin
result:=2;
if (not e(X,Y,T,R)) and (not e(X,Z,T,R)) and (not e(Y,Z,T,R))
and (t1(T,X,Y,Z)) and (l(X,T)>R) and (l(Y,T)>R) and (l(Z,T)>R) then
result:=1;
if (not e(X,Y,T,R)) and (not e(X,Z,T,R)) and (not e(Y,Z,T,R))
and (t1(T,X,Y,Z)) and (L(X,T)<R) and (L(Y,T)<R) and (L(Z,T)<R) then result:=0;
if (not e(X,Y,T,R)) and (not e(X,Z,T,R)) and (not e(Y,Z,T,R))
and (not t1(T,X,Y,Z)) then result:=0;
end;

procedure okr;
var i:integer;
begin
form3.image1.Canvas.Brush.Style:=bsClear;
for i:=1 to form1.stringgrid1.ColCount-1 do
form3.image1.Canvas.Ellipse(Trunc(T[i].x*5+202+R*5),Trunc(R*5+202-T[i].y*5),Trunc(T[i].x*5+198-R*5),Trunc(198-R*5-T[I].y*5));
end;

procedure pix;
var i:integer;
begin
for i:=1 to form1.stringgrid1.ColCount-1 do
form3.image1.canvas.Ellipse(Trunc(T[i].x*5+202),Trunc(202-T[I].y*5),Trunc(T[i].x*5+198),Trunc(198-T[I].y*5));
end;

procedure tre(A,B,C:error);
begin
with form3.image1.Canvas do
begin
pen.Color:=clblue;
MoveTo(trunc(A.x*5+200),trunc(200-A.y*5));
LineTo(trunc(B.x*5+200),trunc(200-B.y*5));
LineTo(trunc(C.x*5+200),trunc(200-C.y*5));
LineTo(trunc(A.x*5+200),trunc(200-A.y*5));
pen.Color:=clblack;
end;
end;

procedure osi;
begin
with form3.image1.Canvas do
begin
MoveTo(200,200);
LineTo(200,400);
MoveTo(200,200);
LineTo(200,0);
MoveTo(200,200);
LineTo(0,200);
MoveTo(200,200);
LineTo(400,200);
end;
end;

procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
stringgrid1.Cells[0,1]:='    x';
stringgrid1.Cells[0,2]:='    y';
for i:=1 to (stringgrid1.ColCount-1) do
begin
stringgrid1.Cells[i,0]:=IntToStr(i);
end;
end;

procedure TForm1.N2Click(Sender: TObject);
begin
form2.Close;
end;

procedure TForm1.Edit1Change(Sender: TObject);
var i,q:integer;
begin
if edit1.Text='' then
edit1.Text:=inttostr(Random(6)+3);
q:=strtoint(edit1.Text);
if q>9 then
begin
edit1.Text:=inttostr(9);
q:=9;
end;
if q<3 then
begin
edit1.Text:=inttostr(3);
q:=3;
end;
stringgrid1.Width:=(42+39*q);
stringgrid1.ColCount:=q+1;
for i:=1 to q do
begin
stringgrid1.Cells[i,0]:=IntToStr(i);
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
for i:=1 to stringgrid1.ColCount-1 do
begin
stringgrid1.Cells[i,1]:=IntToStr(Random(80)-40);
stringgrid1.Cells[i,2]:=IntToStr(Random(80)-40);
end;
end;

procedure TForm1.N3Click(Sender: TObject);
var i:integer;
begin
for i:=1 to stringgrid1.ColCount-1 do
begin
stringgrid1.Cells[i,1]:='';
stringgrid1.Cells[i,2]:='';
end;
end;

From Stilet: А код оформить читабельно судьба не позволяет?

[surovii]

Procedure TForm1.Button2Click(Sender: TObject);
var i,j,k,p:integer;
nv:integer;
ns:integer;
na:integer;
re:boolean;
begin
for i:=1 to stringgrid1.ColCount-1 do
for j:=1 to 2 do
begin
if stringgrid1.Cells[i,j]='' then
begin
showMessage('Надо ввести координаты');
break;
end;
end;
form3.Visible:=true;
for i:=1 to stringgrid1.ColCount-1 do
begin
T[i].x:=strtofloat(stringgrid1.Cells[i,1]);
T[i].y:=strtofloat(stringgrid1.Cells[i,2]);
end;
R:=strtofloat(edit2.Text);
re:=false;
for i:=1 to stringgrid1.ColCount-3 do
for j:=i+1 to stringgrid1.ColCount-2 do
for k:=j+1 to stringgrid1.ColCount-1 do
begin
nv:=0;
ns:=0;
for p:=1 to stringgrid1.ColCount-1 do
begin
if k1(T[p],R,T[i],T[j],T[k])=1 then nv:=nv+1;
if k1(T[p],R,T[i],T[j],T[k])=0 then ns:=ns+1;
end;
if (re=true) and (abs(nv-ns)<na) and ((nv<>0)or(ns<>0)) then
begin
na:=abs(nv-ns);
re:=true;
num[1]:=i;
num[2]:=j;
num[3]:=k;
end;
if (re=false) and ((nv<>0)or(ns<>0)) then
begin
na:=abs(nv-ns);
re:=true;
num[1]:=i;
num[2]:=j;
num[3]:=k;
end;
end;
if re=false then
begin
label3.font.color:=clRed;
label3.caption:='Подходящих точек не найдено!!!';
label4.caption:='';
end
else
begin
label3.font.color:=clBlue;
label3.caption:='Вершины треугольника: '+IntToStr(Num[1])+', '+IntToStr(Num[2])+', '+IntToStr(Num[3]);
label4.Caption:='Разность кол-ва окр-тей лежащих внутри треугольника и снаружи: ' +IntToStr(Na);
form3.image1.Refresh;
form3.image1.Canvas.Brush.Style:=bssolid;
form3.Image1.Canvas.Rectangle(0,0,400,400);
osi;
okr;
pix;
if re=true then tre(T[num[1]],T[num[2]],T[num[3]]);
end;
end;


procedure TForm1.N4Click(Sender: TObject);
var i,num:integer;
begin
if OpenDialog1.Execute then
begin
if FileExists(OpenDialog1.FileName) then
begin
AssignFile(f1,OpenDialog1.FileName);
Reset(f1);
num:=0;
while not EOF(f1) do
begin
num:=num+1;
read(f1,comp);
StringGrid1.Cells[num,1]:= FloatToStr(comp.g);
StringGrid1.Cells[num,2]:= FloatToStr(comp.h);
edit2.Text:=floattostr(comp.j);
end;
edit1.Text:=inttostr(num);
CloseFile(f1);
end;
end;
end;

procedure TForm1.N5Click(Sender: TObject);
var i,num:integer;
begin
num:=strtoint(edit1.text);
if SaveDialog1.Execute then
begin
AssignFile(f,SaveDialog1.FileName);
Rewrite(f);
for i:=1 to num do
begin
comp.g:=StrToint(StringGrid1.Cells[i,1]);
comp.h:=StrToint(StringGrid1.Cells[i,2]);
comp.j:=strtoint(edit2.text);
write(f,comp);
end;
CloseFile(f);
end;
end;

end.