Из заданного на плоскости множества точек выбрать три различные точки

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

code: #cpp
  1. #include
  2. #include
  3. #include
  4. #include
  5. #include
  6. #define NPnt 10
  7. #define XY 2
  8. #define PI 3.141592653589
  9. using namespace std;
  10.  
  11. void randomfill(double(*)[XY]);
  12. void matrix_print(double(*)[XY]);
  13. inline double geron(double,double,double);
  14. long factorial(int);
  15. inline int combination(int,int);
  16. inline double vectormod(double,double,double,double);
  17.  
  18. struct Circle
  19. {
  20.     double rad;
  21.     double area;
  22. };
  23.  
  24. struct Triangle
  25. {
  26.     int i;
  27.     int j;
  28.     int k;
  29.     double a;
  30.     double b;
  31.     double c;
  32.     double area;
  33. };
  34.  
  35. int main() {
  36.     double crd[NPnt][XY];
  37.     int N = combination(NPnt,3);
  38.     Circle MasC[N];
  39.     Triangle MasT[N];
  40.     int cnt = 0;
  41.     srand(time(NULL));
  42.     randomfill(crd);
  43.     matrix_print(crd);
  44.     for(int i = 0; i < (NPnt-2); i++)
  45.         for(int j = i+1; j < (NPnt-1); j++)
  46.             for(int k = j+1; k < NPnt; k++)
  47.             {
  48.                 MasT[cnt].a = vectormod(crd[i][0],crd[j][0],crd[i][1],crd[j][1]);
  49.                 MasT[cnt].b = vectormod(crd[j][0],crd[k][0],crd[j][1],crd[k][1]);
  50.                 MasT[cnt].i = i; MasT[cnt].j = j; MasT[cnt].k = k;
  51.                 MasT[cnt++].c = vectormod(crd[i][0],crd[k][0],crd[i][1],crd[k][1]);
  52.             }
  53.     for(int i = 0; i < N; i++)
  54.     {
  55.         MasT[i].area = geron(MasT[i].a,MasT[i].b,MasT[i].c);
  56.         MasC[i].rad = (MasT[i].a * MasT[i].b * MasT[i].c)/(4*MasT[i].area);
  57.         MasC[i].area = PI * MasC[i].rad * MasC[i].rad;
  58.     }
  59.     int buf[3] = {0,1,2};
  60.     double min_diff = 1E18;
  61.     for(int i = 0; i < N; i++)
  62.     {
  63.         double temp = MasC[i].area - MasT[i].area;
  64.         if(temp < min_diff)
  65.         {
  66.             min_diff = temp;
  67.             buf[0] = MasT[i].i;
  68.             buf[1] = MasT[i].j;
  69.             buf[2] = MasT[i].k;
  70.         }
  71.     }
  72.  
  73.     cout << "Были сделаны вычисления:" << endl;
  74.     cout << "Минимальная разность в площадях была на точках:" << endl << endl;
  75.     for(int i = 0; i < 3; i++)
  76.         cout << crd[buf[i]][0] << " " << crd[buf[i]][1] << endl << endl;
  77.     return 0;
  78. }
  79.  
  80. void randomfill(double mtx[][XY])
  81. {
  82.     for(int i = 0; i < NPnt; i++)
  83.         for(int j = 0; j < XY; j++)
  84.             mtx[i][j] = rand()%31 - 15;
  85. }
  86.  
  87. void matrix_print(double mtx[][XY])
  88. {
  89.     cout << "Печатаю координаты:" << endl;
  90.     cout << setw(5) << "X " << setw(4) << "Y " << endl << endl;
  91.     for(int i = 0; i < NPnt; i++)
  92.     {
  93.         for(int j = 0; j < XY; j++)
  94.             cout << setw(4) << mtx[i][j];
  95.         cout << endl;
  96.     }
  97. }
  98.  
  99. inline double geron(double a,double b,double c)
  100. {
  101.      return 0.25*sqrt((a+b+c)*(b+c-a)*(a+c-b)*(a+b-c));
  102. }
  103.  
  104. long factorial(int N)
  105. {
  106.     if(!N) return 1;
  107.     long result = 1;
  108.     for(int i = 1; i <= N; i++)
  109.         result *= i;
  110.     return result;
  111. }
  112.  
  113. inline int combination(int n, int k)
  114. {
  115.     return (factorial(n)/(factorial(k)*factorial(n-k)));
  116. }
  117.  
  118. inline double vectormod(double x1, double x2, double y1, double y2)
  119. {
  120.     return (sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)));
  121. }
Поделиться:

Похожие статьи: