1 Востаннє редагувалося koala (06.08.2014 21:58:40)

Тема: Нащо потрібні АТД. Маленький приклад (чи майстерклас), геометрія.

Отже, є задача:

Задані координати трьох вершин прямокутника. Необхідно знайти координати четвертої вершини.

деталі

Вхідні дані
У файлі INPUT.TXT через пробіл записані координати трьох верши прямокутника у випадковому порядку в форматі x1 y1 x2 y2 x3 y3. Всі числа цілі додатні, не більші за 10000.
Вихідні дані
У вихідний файл OUTPUT.TXT треба вивести через пробіл координати x y четвертої вершини прямокутника.

Мені тут дуже подобається векторний розв'язок. Позначимо вершину, що знаходиться навпроти невідомої, через B, невідому - D (дві інші тоді - A і C), і так само позначимо вектори з початку координат до цих вершин (щоб координати були однакові). Тоді маємо векторну суму D = B + ( C - B ) + ( A - B ) = C + A - B. Але як визначити, яка з трьох введених вершин лежить навпроти невідомої? Дуже просто - скалярний добуток перпендикулярних векторів дорівнює 0:
( B - A ) * ( B - C ) = 0.
Отже, намалювався алгоритм:
1. Ввести A, B, C;
2. Знайти, хто з них B.
3. Знайти за формулою D.
4. Вивести D.

Записуємо:
#include <fstream>
#include <algorithm>

int main()
{
  //Ввести A, B, C;
  std::ifstream in("input.txt");
  std::ofstream out("output.txt");
  Vector a, b, c;
  in >> a >> b >> c;
  //Знайти, хто з них B.
  if( ( a - b ) * ( a - c ) == 0 )
    std::swap( a, b );
  else if( ( a - c ) * ( b - c ) == 0 )
    std::swap( b, c );
  //Знайти за формулою D. Вивести D.
  out << ( c +  a - b );
}

Для того, щоб b "став на місце", я використав стандартний std::swap. Змінну D навіть не став проголошувати - все одно вона потрібна тільки для виводу.
Ну що, все чудово, але класу Vector поки що не існує, про що нам при спробі побудувати нагадає компілятор: [Error] 'Vector' was not declared in this scope.

Виправимо це:
class Vector
{
  int x, y;
};

Тепер компілятор скаржится, що не знає, як вводити наш вектор: [Error] no match for 'operator>>' in 'in >> a'. Не проблема,

додаємо відповідний оператор (і одразу оператор виводу):
class Vector
{
  int x, y;
  friend std::istream& operator >>( std::istream&, Vector& );
  friend std::ostream& operator <<( std::ostream&, const Vector& );
};

std::istream& operator >>( std::istream& is, Vector &v )
{
   return is >> v.x >> v.y;
}

std::ostream& operator <<( std::ostream &os, const Vector &v )
{
   return os << v.x << " " << v.y;
}

Все чудово, оператор введення вводить наш вектор в тому форматі, в якому він записаний у вхідному файлі, оператор виведення так само виводить. Обидва проголошені друзями, щоб мати доступ до приватних змінних x та y. Наступна проблема - [Error] no match for 'operator-' in 'a - b' . Віднімати вектори ми його поки що не навчили!

Виправляємо:
class Vector
{
  int x, y;

  public:
  Vector operator - ( Vector other ) const; 

  friend std::istream& operator >>( std::istream&, Vector& );
  friend std::ostream& operator <<( std::ostream&, const Vector& );
};

Vector Vector::operator - ( Vector other ) const
{
  Vector result(*this);
  result.x -= other.x;
  result.y -= other.y;
  return result; 
}

const наприкінці означає, що цей оператор може застосовуватися до константних векторів - він їх не змінює. Зверніть увагу, що цей оператор має бути публічним, інакше ми не зможемо віднімати вектори. Ну а що він робить - ніби очевидно: віднімає вектори за правилами. Друзів теж перенесено в розділ public - просто для порядку, це публічна операція і її зручніше показати серед інших публічних (хоча й не має значення, де її прописують, вона все одно не член класу). Пішли далі: [Error] no match for 'operator*' in 'a.Vector::operator-(b) * a.Vector::operator-(c)'

Ой-ой-ой! Віднімати навчили, а множити хто їх буде? Ми!
class Vector
{
  int x, y;

  public:
  Vector operator - ( Vector other ) const; 
  int operator * ( Vector other ) const;

  friend std::istream& operator >>( std::istream&, Vector& );
  friend std::ostream& operator <<( std::ostream&, const Vector& );
};

int Vector::operator * ( Vector other ) const
{
  return x * other.x + y * other.y;
}

Нема чого коментувати, все за формулою з підручника.

[Error] no match for 'operator +' in 'c + a'. Немає оператора '+'. Не знаю, як вам, а мені ліньки ще один оператор писати. Змінюємо формулу:
c +  a - b = c - ( b - a ):

out << ( c - ( b - a ) );

Все!

Готовий результат
#include <fstream>
#include <algorithm>

class Vector
{
  double x, y;
  friend std::istream& operator >>( std::istream&, Vector& );
  friend std::ostream& operator <<( std::ostream&, const Vector& );

  public:
  Vector operator - ( Vector other ) const;
  int operator * ( Vector other ) const;
};

std::istream& operator >>( std::istream& is, Vector &v )
{
   return is >> v.x >> v.y;
}

std::ostream& operator <<( std::ostream &os, const Vector &v )
{
   return os << v.x << " " << v.y;
}


Vector Vector::operator - ( Vector other ) const
{
  Vector result( *this );
  result.x -= other.x;
  result.y -= other.y;
  return result; 
}

int Vector::operator * ( Vector other ) const
{
  return x * other.x + y * other.y;
}

int main()
{
  std::ifstream in("input.txt");
  std::ofstream out("output.txt");
  Vector a, b, c;
  in >> a >> b >> c;
  if( ( a - b ) * ( a - c ) == 0 )
    std::swap( a, b );
  else if( ( a - c ) * ( b - c ) == 0 )
    std::swap( b, c );
  out << ( c - ( b - a ) );
}

Ну от, створили новий простенький тип для розв'язання задачі в тих поняттях і термінах, в яких вона розв'язується найлегше, і розв'язали шкільними формулами. На все - 20 хвилин. Скільки часу вам знадобиться, щоб розв'язати це без векторів?

Подякували: Joker, Chemist-i, quez4

2

Re: Нащо потрібні АТД. Маленький приклад (чи майстерклас), геометрія.

Спасибі величезне. Як раз подібне завдання в індивідуальних попалася. прям супер просто. Ще раз величезне спасибі!