Пересечение прямых

Опубликовано Sep 30, 2011 в Математика и логика | 8 коммент.

, , ,

Напишите класс Line, реализующий прямую линию в декартовом пространстве.
Напишите для этого класса метод, который бы проверял, пересекаются ли две линии.

class Line
{
   // ваш код
 public: bool line_intersection(const Line line) const
  {
    bool result;
    // ваш код
    return result;
  }
};
1 Цель задания проверка базовых знаний элементарной математики вместе с простейшими приемами ООД
2 Время выполнения от 10 минут для двумерного случая до 30 мин для многомерного
3 Формат выполнения код пишется на листике, без доступа к документации

Критерии оценки FulcrumWeb:

Кандидат должен первым делом понять, что в условии не указана размерность пространства и обязательно задать вопрос об этом, иначе вообще не ясно какие поля создавать.

Ожидаемые вопросы:

  1. Можно ли считать пространство двумерным, трехмерным или оно имеет произвольную размерность?
  2. Какая требуется точность при решении задачи?
  3. Есть ли четкое требование по поводу того, каким уравнением описывать прямую, если пространство имеет размерность 2?
  4. Если решение будет реализовано для n-мерного случая, то можно ли считать, что уже имеется реализация вспомогательного класса ВЕКТОР, который управляет своим распределением памяти с готовыми методами для математических операций скалярного и векторного произведения?
  5. Если решение будет реализовано для n-мерного случая, то можно ли использовать подходящие контейнеры из STL при отсутствии класса из предыдущего пункта ?
  6. Как трактовать случай, когда прямая пересекается сама с собой?

Оценка результатов:

Вопрос о размерности пространства должен быть задан обязательно. Если на него дан однозначный ответ, что n = 2 или 3, то эту информацию стоит использовать и не вводить динамических структур данных.
Вопрос о точности вычислений также должен быть поднят, так как задача подразумевает сравнение вещественных чисел.

Для юниора приемлемым является решение, при котором он сам без вопросов додумал, что n = 2. Если при этом он видит, что и где нужно изменить, если размерность возрастет – это совсем хорошо. Но мы надеемся не увидеть применения оператора == к операндам типа double, а также, что не будет упущена ситуация, связанная с последним вопросом.

От программистов с опытом работы мы ожидаем услышать вопросы из приведенного выше перечня, причем задаваемые с учетом ответов на предыдущие вопросы. То есть оценивается умение работать с требованиями и их уточнять. Достоинства решения самого общего вида совсем без вопросов кажутся нам спорными, так как, возможно, что создается система обучения школьников планиметрии.


8 Коммент. : “Пересечение прямых”

  1. Олька says:

    Есть декартова система координат,
    есть декартова система координат в пространстве
    а что значит декартово пространство?

    • “Декартово пространство” – это более короткое название пространства с введенной в нем декартовой системой координат.

  2. Сергей says:

    “Достоинства решения самого общего вида совсем без вопросов кажутся нам спорными, так как, возможно, что создается система обучения школьников планиметрии.”

    Поясните эту фразу, пожалуйста.

    • “…создается система обучения школьников планиметрии” – планиметрия, значит n = 2 и только 2. Вряд ли стоит использовать динамические структуры данных для хранения многомерных координат точки (общий случай) для этого. Лучше из STL – std::pair, или свой похожий класс/структура.

  3. Привожу решение для двумерного пространства. Завтра переделаю для многомерного.
    Line2D.h

    #ifndef _LINE2D_H_
    #define _LINE2D_H_
     
    #include <iostream>
    using namespace std;
    // Line on the plane (2D)
    // We represent line using formula Ax+By+C=0
    class Line
    {
    private:
    	double A;
    	double B;
    	double C;
    public:
    	Line::Line(double a = 1, double b = 1, double c = 1):
    	  A(a), B(b), C(c)
    	  {	  }
    	Line& operator=(const Line& ln);
    	void ShowFormula();
    	bool LineIntersection(const Line line) const;
    	friend ostream& operator<<(ostream& out, const Line& ln);
    };
    #endif

    Line2D.cpp

    #include "Line2D.h"
    #include <iostream>
    using namespace std;
    static const double SMALL_NUMBER = 0.000000000001;
    inline bool FloatNumbersAreEqual(double a, double b)
    {
    	return (fabs((a) - (b)) < SMALL_NUMBER);
    }
     
    Line& Line::operator=(const Line& ln)
    {
    	A = ln.A;
    	B = ln.B;
    	C = ln.C;
    	// Is this good?
    	return *this;
    }
    void Line::ShowFormula()
    {
    	cout << endl << A << 'x';
    	if(B > 0) 
    	{
    		cout << '+' << B << 'y';
    	}
    	else if(B < 0)
    	{
    		cout << B << 'y';
    	}
    	if(C > 0)
    	{
    		cout << '+' << C;
    	}
    	else if(C < 0)
    	{
    		cout << C;
    	}
    	cout << "=0;";
    }
    bool Line::LineIntersection(const Line line) const
    {
    	bool result;
    	if(false == FloatNumbersAreEqual(A/line.A, B/line.B))
    	{
    		result = true;
    	}
    	else
    	{
    		result = false;
    	}
    	return result;
    }

    main.cpp

    #include <iostream>
    #include "Line2D.h"
    using namespace std;
    ostream& operator<<(ostream& out, const Line& ln)
    {
    	out << endl << ln.A << 'x';
    	if(ln.B > 0)
    	{
    		out << '+' << ln.B << 'y';
    	}
    	else if(ln.B < 0)
    	{
    		out << ln.B << 'y';
    	}
    	if(ln.C > 0)
    	{
    		out << '+' << ln.C;
    	}
    	else if(ln.C < 0)
    	{
    		out << ln.C;
    	}
    	out << "=0;";
    	return out;
    }
    int main()
    {
    	Line firstLine(3.5, -2.5, -1);
    	Line secondLine(0);
    	cout << "We've got 2 lines:" << endl
    		<< secondLine << firstLine << endl
    		<< "Lines intersect: "
    		<< boolalpha << secondLine.LineIntersection(firstLine)
    		<< noboolalpha << endl;
    	cin.get();
    	return 0;
    }
    • Галина says:

      Нормальный вариант. Правда метод LineIntersection можно написать короче :)

      bool Line::LineIntersection(const Line line) const
      {
      	return ! FloatNumbersAreEqual(A/line.A, B/line.B);
      };
      
      • Согласен с вами, конечно нужно было укоротить, использовать тернарный оператор. Я просто исходил из того, что кусок тела был задан в условии задачи.

  4. Чуть не забыл выложить вариант для прямых в многомерном пространстве. Кода много, но суть остаётся та же самая.
    LineND.h

    #ifndef _LINEND_H_
    #define _LINEND_H_
     
    #include <iostream>
    #include <cmath>
    #include <vector>
    using namespace std;
     
    const char COEF_LETTER[] = 
    {   'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
    	'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u',
    	'v', 'w', 'x', 'y', 'z'
    };
    static const double SMALL_NUMBER = 0.000000000001;
    inline bool FloatNumbersAreEqual(double a, double b)
    {
    	return (fabs((a) - (b)) < SMALL_NUMBER);
    }
     
    // We represent line using formula Ax+By+...+C=0
    class LineND
    {
    private:
    	vector<double> coefficients;
    public:
    	LineND(int dimension, double a ...);
    	LineND& operator=(const LineND& ln);
    	void ShowFormula();
    	bool LineIntersection(const LineND line) const;
    	friend ostream& operator<<(ostream& out, const LineND& ln);
    };
     
    #endif

    LineND.cpp

    #include "LineND.h"
    #include <cstdarg>
    LineND::LineND(int dimension, double a ...)
    {
    	va_list arguments;
    	va_start(arguments, dimension);
    	double argValue;
    	do
    	{
    		argValue = va_arg(arguments, double);
    		coefficients.push_back(argValue);
    		dimension--;
    	}while(dimension > 0);
    	va_end(arguments);
    }
    LineND& LineND::operator=(const LineND& ln)
    {
    	coefficients.clear();
    	coefficients.resize(ln.coefficients.size());
    	coefficients.assign(ln.coefficients.begin(), ln.coefficients.end());
    	return *this;
    }
    void LineND::ShowFormula()
    {
    	cout << endl << coefficients[0] << COEF_LETTER[0];
    	for(int i = 1; i < coefficients.size()-1; i++)
    	{
    		if(coefficients[i] > 0)
    		{
    			cout << '+' << coefficients[i] << COEF_LETTER[i];
    		}
    		else if(coefficients[i] < 0)
    		{
    			cout << coefficients[i] << COEF_LETTER[i];
    		}
    	}
    	if(coefficients[coefficients.size()-1] > 0)
    	{
    		cout << '+' << coefficients[coefficients.size()-1];
    	}
    	else if(coefficients[coefficients.size()-1] < 0)
    	{
    		cout << coefficients[coefficients.size()-1];
    	}
    	cout << "=0;";
    }
    bool LineND::LineIntersection(const LineND line) const
    {
    	bool result;
    	if(line.coefficients.size() != coefficients.size())
    	{
    		result = false;
    	}
    	else
    	{
    		double coefRelation = coefficients[0] / line.coefficients[0];
    		int equalPairs = 0;
    		for(int i = 1; i < (coefficients.size()-1); i++)
    		{
    			if(FloatNumbersAreEqual(coefRelation, coefficients[i]/ line.coefficients[i]) == true)
    			{
    				equalPairs++;
    			}
    		}
    		if(equalPairs != coefficients.size()-2)
    		{
    			result = false;
    		}
    		else
    		{
    			result = true;
    		}
    	}
    	return result;
    }

    main.cpp

    #include "LineND.h"
    ostream& operator<<(ostream& out, const LineND& ln)
    {
    	out << endl << ln.coefficients[0] << COEF_LETTER[0];
    	for(int i = 1; i < ln.coefficients.size()-1; i++)
    	{
    		if(ln.coefficients[i] > 0)
    		{
    			out << '+' << ln.coefficients[i] << COEF_LETTER[i];
    		}
    		else if(ln.coefficients[i] < 0)
    		{
    			out << ln.coefficients[i] << COEF_LETTER[i];
    		}
    	}
    	if(ln.coefficients[ln.coefficients.size()-1] > 0)
    	{
    		out << '+' << ln.coefficients[ln.coefficients.size()-1];
    	}
    	else if(ln.coefficients[ln.coefficients.size()-1] < 0)
    	{
    		out << ln.coefficients[ln.coefficients.size()-1];
    	}
    	out << "=0;";
    	return out;
    }
    int main()
    {
    	LineND firstLine(6, 3.5, -2.5, -1.0, 5.2, 3.0, 5.0);
    	LineND secondLine(6, 7.0, -5.0, -2.0, -1.0, -2.0, -3.0);
    	cout << "We've got 2 lines:" << endl
    		<< secondLine << firstLine << endl
    		<< "Lines intersect: "
    		<< boolalpha << secondLine.LineIntersection(firstLine)
    		<< noboolalpha << endl;
    	cin.get();
    	return 0;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*