C++ Builder Графика

Lers

New Member
03.06.2013
1
0
#1
Определить радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества.
Вот задача к этому условию:
C++:
#include <vcl.h>
#include <math.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int mas1[2][100];
int kol1 = 0;
int mas2[2][100];
int kol2 = 0;

typedef struct CIRCLE		 //typedef
{
double x;
double y;
double r;
} circle;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
osi_drawed = false;
}
//---------------------------------------------------------------------------
void Osi_X_Y(TPaintBox *PB1)
{
int x0, y0;
x0 = PB1->Width/2;
y0 = PB1->Height/2;
PB1->Canvas->Pen->Color = clSilver;
PB1->Canvas->MoveTo(0,y0);
PB1->Canvas->LineTo(PB1->Width,y0);
PB1->Canvas->MoveTo(x0,0);
PB1->Canvas->LineTo(x0,PB1->Height);
PB1->Canvas->Pen->Color = clRed;

}
//---------------------------------------------------------------------------
void __fastcall TForm1::Random_X_Y()
{
int x, y;
//randomize();
//rand();
x = random(PaintBox1->Width-100);
y = random(PaintBox1->Height-100);
PaintBox1->Canvas->Ellipse(x-2,y-2,x+2,y+2);
x -= PaintBox1->Width/2;
y = PaintBox1->Height/2 - y;
kol1++;
mas1[0][kol1-1] = x;
mas1[1][kol1-1] = y;
StringGrid1->Cells[0][kol1-1] = IntToStr(x);
StringGrid1->Cells[1][kol1-1] = IntToStr(y);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Manually_X_Y(int x, int y)
{
int x0, y0;
x0 = PaintBox1->Width/2;
y0 = PaintBox1->Height/2;
x0 += x;
y0 -= y;
PaintBox1->Canvas->Ellipse(x0-2,y0-2,x0+2,y0+2);
kol1++;
mas1[0][kol1-1] = x;
mas1[1][kol1-1] = y;
StringGrid1->Cells[0][kol1-1] = IntToStr(x);
StringGrid1->Cells[1][kol1-1] = IntToStr(y);
}
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
if (!osi_drawed)
{
Osi_X_Y(PaintBox1);
osi_drawed = true;
}

Manually_X_Y(StrToInt(LabeledEdit1->Text), StrToInt(LabeledEdit2->Text));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::DrowT(int x1, int x2, int x3, int y1, int y2, int y3)
{
int x0, y0;
x0 = PaintBox1->Width/2;
y0 = PaintBox1->Height/2;
TColor c = PaintBox1->Canvas->Pen->Color;
PaintBox1->Canvas->Pen->Color = clBlue;
PaintBox1->Canvas->MoveTo(x1 + x0, y0 - y1);
PaintBox1->Canvas->LineTo(x2 + x0, y0 - y2);
PaintBox1->Canvas->LineTo(x3 + x0, y0 - y3);
PaintBox1->Canvas->LineTo(x1 + x0, y0 - y1);
PaintBox1->Canvas->Pen->Color = c;
}
//---------------------------------------------------------------------------

inline double det(
double a1, double b1, double c1,
double a2, double b2, double c2 )
{
double d = (a1*a1+a2*a2)*b2 + (b1*b1+b2*b2)*c2 + (c1*c1+c2*c2)*a2;
d -= (a1*a1+a2*a2)*c2 + (b1*b1+b2*b2)*a2 + (c1*c1+c2*c2)*b2;
return d;
}

inline double norm(double x1, double y1, double x2, double y2)
{
double x = x1 - x2;
double y = y1 - y2;
return sqrt(x*x+y*y);
}

circle cir(
double x1, double y1,
double x2, double y2,
double x3, double y3 )
{
circle crcl;
double a = norm(x1, y1, x2, y2);
double b = norm(x1, y1, x3, y3);
double c = norm(x3, y3, x2, y2);
double Dinv = 0.5;
if ((x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))!=0)
Dinv = 0.5/(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
else
{
//ShowMessage("Tochki na odnoi pryamoi");
}
crcl.r = a*b*c*fabs(Dinv);
crcl.x = Dinv*det(x1, x2, x3, y1, y2, y3);
crcl.y = -Dinv*det(y1, y2, y3, x1, x2, x3);
return crcl;
}

void __fastcall TForm1::Button1Click(TObject *Sender)
{
Memo2->Clear();
circle c;
circle big_circle;

int i, j, k, m, t1=0,t,kolElem2 = 0, kolElem1 = 0;
int n=kol1; //типичный велосипед
for (i=0; i<n-2; i++)
for (j=i+1; j<n-1; j++)
for (k=j+1; k<n; k++)
{
c = cir(
mas1[0][i], mas1[1][i],
mas1[0][j], mas1[1][j],
mas1[0][k], mas1[1][k] );
//проверка точек
t=0;
for (m=0; m<n; m++)
{
if ((mas1[0][m]-c.x)*(mas1[0][m]-c.x) + (mas1[1][m]-c.y)*(mas1[1][m]-c.y) < c.r*c.r) t++;
}
if (t>t1)
{
t1=t;
big_circle = c;

Memo2->Lines->Add("Center: "+FloatToStrF(big_circle.x,ffFixed,3,2)+", "+FloatToStrF(big_circle.y,ffFixed,3,2));
Memo2->Lines->Add("Radius: "+FloatToStrF(big_circle.r,ffFixed,3,2));
Memo2->Lines->Add("Points inside: "+IntToStr(t1));
Memo2->Lines->Add(" ");
}
}
PaintBox1->Canvas->Pen->Color=clGreen;
PaintBox1->Canvas->Brush->Style=bsClear;

int x0 = PaintBox1->Width/2;
int y0 = PaintBox1->Height/2;
x0 += big_circle.x;
y0 -= big_circle.y;
int rad=big_circle.r;
PaintBox1->Canvas->Ellipse(x0-rad,y0-rad,x0+rad,y0+rad);
PaintBox1->Canvas->Pen->Color=clRed;

}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button3Click(TObject *Sender)
{
if (!osi_drawed)
{
Osi_X_Y(PaintBox1);
osi_drawed = true;
}
Random_X_Y();
}
//---------------------------------------------------------------------------

void __fastcall TForm1::FormShow(TObject *Sender)
{
UpDown1->Max = PaintBox1->Width/2;
UpDown1->Min = -PaintBox1->Width/2;
UpDown2->Max = PaintBox1->Height/2;
UpDown2->Min = -PaintBox1->Height/2;

}
//---------------------------------------------------------------------------
помогите переделать эту задачу под это условие:
Даны два множества точек на плоскости. Найти центр и радиус окружности, проходящей через к (к> 3) точек первого множества и содержащей внутри себя m точек второго множества.
P.S. ввод второго множества не проблема, основная проблема эта переписать cir для общего случая.