Примеры решений задач

Задача "Вектор"

Вычислить длину вектора $\overrightarrow{a}=(x,y,z)$

Решение

Длина вектора: $|\overrightarrow{a}| = \sqrt{x^2+y^2+z^2}$

#include <stdio.h>
#include <math.h>

int main(){
  // Открываем входной и выходной файл
  freopen("vector.in","r",stdin);
  freopen("vector.out","w",stdout);

  // Ввод данных
  double x, y, z;
  scanf("%lf %lf %lf", &x, &y, &z);

  // Вычисления и вывод ответа
  printf("%.2lf\n", sqrt(x*x + y*y + z*z));

  return 0;
}
    

Задача "Прямая по 2-м точкам"

$a{x_1}+b{y_1}+c=0$ - первая точка
$a{x_2}+b{y_2}+c=0$ - вторая точка

Решить систему из 2-х линейных уравнений с 3-мя неизвестными => бесконечное количество решений (это одна прямая, и коэффициенты $a, b, c$ у всех решений пропорциональны друг другу).

$a = \frac{-b{y_1}-c}{x_1}$

$\frac{-b{y_1}-c}{x_1} {x_2}+b{y_2}+c=0$

$-b{y_1}{x_2}-c{x_2}+b{y_2}{x_1}+c{x_1}=0$

$b({y_2}{x_1}-{y_1}{x_2})+c({x_1}-{x_2})=0$

$c = 1$

$b({y_2}{x_1}-{y_1}{x_2})+c({x_1}-{x_2})=0$

$b = \frac{ {x_2}-{x_1} } {{y_2}{x_1}-{y_1}{x_2}}$; $c = 1$; $a = \frac{- c - b{y_1}}{x_1}$

Умножим все уравнения на: ${{y_2}{x_1}-{y_1}{x_2}}$

$b = {x_2}-{x_1}$; $c = {{y_2}{x_1}-{y_1}{x_2}}$; $a = \frac{{- c - b{y_1}}}{x_1}{({{y_2}{x_1}-{y_1}{x_2}})}$

$a = \frac{{- ({{y_2}{x_1}-{y_1}{x_2}}) - ({x_2}-{x_1}){y_1}}}{x_1}{({{y_2}{x_1}-{y_1}{x_2}})}$

$a = \frac{{- {y_2}{x_1} + {y_1}{x_2} - {x_2}{y_1} + {x_1}{y_1}}} {x_1}{({{y_2}{x_1}-{y_1}{x_2}})}$

$a = ({y_1} - {y_2}) {({{y_2}{x_1}-{y_1}{x_2}})}$

Это частичное решение, оно работает не во всех случаях (надо отдельно разбирать когда ${y_2}{x_1}-{y_1}{x_2}=0$ ).

Другой вариант решения (для всех случаев)

$a{x_1}+b{y_1}+c=0$ - первая точка
$a{x_2}+b{y_2}+c=0$ - вторая точка

Приравниваем уравнения или вычитаем из первого уравнения второе.

Получаем уравнение с двумя неизвестными: $a({x_1}-{x_2})+b({y_1}-{y_2}) = 0$

Интуиция подсказывает решение:
$a = {y_1}-{y_2}$
$b = -({x_1}-{x_2})$
$({y_1}-{y_2})({x_1}-{x_2})-({x_1}-{x_2})({y_1}-{y_2}) = 0$

$c = -(a{x_1}+b{y_1}) = -a{x_1}-b{y_1} = -({y_1}-{y_2}){x_1}+({x_1}-{x_2}){y_1} = -\underline{{y_1}{x_1}}+{y_2}{x_1}+\underline{{x_1}{y_1}}-{x_2}{y_1}={y_2}{x_1}-{x_2}{y_1}$

#include <stdio.h>
#include <math.h>

int main(){
  // Открываем входной и выходной файл
  freopen("line.in","r",stdin);
  freopen("line.out","w",stdout);

  // Ввод данных
  double x1, y1, x2, y2;
  scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);

  double a = y1-y2;
  double b = -(x1-x2);
  double c = -(a*x1+b*y1);

  // Вычисления и вывод ответа
  printf("%.2lf %.2lf %.2lf\n", a, b, c);
  // Проверка ответа
  printf("%.2lf\n", a*x1 + b*y1 + c);
  printf("%.2lf\n", a*x2 + b*y2 + c);

  return 0;
}

#include <stdio.h>
#include <math.h>

const double Inf = 1.e10;

double min(double a, double b){
  return (a < b) ? a : b;
}

int main(){
  // Открываем входной и выходной файл
  freopen("maxdist.in","r",stdin);
  freopen("maxdist.out","w",stdout);

  // Ввод данных
  int N; // Количество вершин 
  scanf("%d", &N);
  double X[100], Y[100];
  for(int i=0; i<N; i++)
    scanf("%lf %lf", &X[i], &Y[i]);

  double D[100][100];

  for(int i=0; i<N; i++)
    for(int j=0; j<N; j++)
      D[i][j] = (i==j) ? 0 : Inf;

  int M; // Количество рёбер
  scanf("%d", &M);
  for(int i=0; i<M; i++){
    int from, to;
    scanf("%d %d", &from, &to);
    from--; to--;

    double dist = sqrt(pow(X[from]-X[to],2) + pow(Y[from]-Y[to],2));
    D[from][to] = dist;
    D[to][from] = dist;
  }  

  // Сам алгоритм 
  for(int k=0; k<N; k++)
    for(int i=0; i<N; i++)
      for(int j=0; j<N; j++)
        D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

  // Выбираем максимум 
  double max1 = 0.0;
  for(int i=0; i<N; i++)
    for(int j=0; j<N; j++){
      if(D[i][j] > max1) {
         max1 = D[i][j];
      }
    }

  if((max1 > 0) && (max1 < Inf)){
    printf("%0.6lf\n", max1);
  } else {
    printf("-1\n");
  }
  
  return 0;
}

Разбор задачи о подобных треугольниках (Пифагор)

Идея решения: перебирать стороны ища среди них пропорциональные.

#include >stdio.h<
#include >iostream<
#include >algorithm<

using namespace std;

// Задача о подобии треугольников

// Треугольники подобны, когда их стороны пропорциональны
// 1 2 3
// 2 6 4
// Стороны должны быть упорядочены по возрастанию
bool similar(int a1, int b1, int c1,
             int a2, int b2, int c2 ){
  return (a1*b2 == b1*a2) && (b1*c2 == c1*b2);
}

int main()
{
    freopen("pifagor.in","r",stdin);
    freopen("pifagor.out","w",stdout);

    // Ввести исходные данные: длины сторон
    int len[9], u[9];
    for(int i=0; i<9; i++){
      cin >> len[i];
      u[i] = 0;
    }

    // Упорядочить (отсортировать) стороны по длине
    sort(len, len + 9);

    // Перебирать стороны и искать подобные треугольники
    // Когда найдём, выведем на экран
    for(int i=0; i<9; i++){
      u[i] = 1;
      for(int j=i+1; j<9; j++){
        u[j] = 1;
        for(int k=j+1; k<9; k++){
          u[k] = 1;
          for(int i2=i+1; i2<9; i2++)
            if(!u[i2]){
              u[i2] = 1;
              for(int j2=j+1; j2<9; j2++)
                if(!u[j2]){
                    u[j2] = 1;
                    for(int k2=k+1; k2<9; k2++)
                      if(!u[k2]){
                        u[k2] = 1;
                        if(similar(len[i],len[j],len[k],
                                   len[i2],len[j2],len[k2])){
                          cout << len[i] << " " << len[j] << " " << len[k] << endl;
                          cout << len[i2] << " " << len[j2] << " " << len[k2] << endl;
                          return 0;
                        }
                        u[k2] = 0;
                      }
                    u[j2] = 0;
                }
              u[i2] = 0;
            }
          u[k] = 0;
        }
        u[j] = 0;
      }
      u[i] = 0;
    }
    return 0;
}