Решение задачи Разбиение треугольника с Другой

С пояснением   Просмотров: 656


Треугольник можно разбить на два треугольника, проведя медиану к его большей стороне (на рисунке сверху такое разбиение показано красным разрезом). Затем два меньших треугольника можно подобным образом разделить на четыре треугольника (на рисунке такое разбиение показано синими разрезами). Процесс разрезания треугольников будем продолжать до бесконечности.

Математики заметили, что при описанном разрезании мы получим конечное количество "стилей" треугольников, которые отличаются друг от друга только размером. По заданным длинам сторон исходного треугольника необходимо определить количество стилей треугольников, которое можно получить. Два треугольника принадлежат одному стилю, если они подобны.

Код

#include <bits/stdc++.h>

using namespace std;

int add(double x1, double y1, double z1)
{
  y1 = y1 / x1; z1 = z1 / x1;
  for(int i = 0; i < ptr; i++)
    if ((fabs(y1 - y[i]) < 0.000001) && (fabs(z1 - z[i]) < 0.000001))
      return 0;
  y[ptr] = y1; z[ptr] = z1;
  return ++ptr;
}

void triangle(double a, double b, double c)
{
  double temp[3] = {a,b,c};
  sort(temp,temp+3);
  if(!add(temp[0],temp[1],temp[2]))
    return;
  double m = sqrt(2*temp[0]*temp[0] + 2*temp[1]*temp[1] – temp[2]*temp[2]) / 2;
  triangle(temp[0],m,temp[2]/2);
  triangle(temp[1],m,temp[2]/2);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(test = 1; test <= n; test++){
      scanf("%lf %lf %lf",&a,&b,&c);
      ptr = 0; triangle(a,b,c);
      printf("Triangle %d: %d\n",test,ptr);
    }
    return 0;
}

         

Администратор Photo Автор: Администратор


https://site.ada.edu.az/~medv/acm/Docs%20e-olimp/Volume%2016/1518.htm



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться