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

Категория: C/C++
2011-08-25 21:56:16

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

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. }
Поделиться:

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

теги: студенты, массив, двумерный массив, окружность, плоскость