C++ Builder Графика

Тема в разделе "C/C++/C#", создана пользователем Lers, 3 июн 2013.

  1. Lers

    Lers New Member

    Регистрация:
    3 июн 2013
    Сообщения:
    1
    Симпатии:
    0
    Определить радиус и центр окружности, проходящей по крайней мере через три различные точки заданного множества точек на плоскости и содержащей внутри наибольшее количество точек этого множества.
    Вот задача к этому условию:
    Код (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 для общего случая.
     
Загрузка...

Поделиться этой страницей