Показать сообщение отдельно
Старый 03.06.2013, 14:19   #1 (permalink)
Lers
Новичок
 
Регистрация: 03.06.2013
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию C++ Builder графика

Определить радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества.
Вот задача к этому условию:
Код:
#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 точек второго множества.
Lers вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070