Вычислительная геометрия

Точка на прямой (одномерное пространство) может задана одной координатой `x`.

Точка на плоскости (2D) может задана двумя координатами `(x,y)` или расстоянием от начала координат и углом `(r,phi)`.

Точка в пространстве (3D) может задана тремя координатами `(x,y,z)` или расстоянием от начала координат и зенитным и азимутальным углами `(r,theta,phi)`.

Перевод из декартовых координат в полярные:

double r=hypot(x,y);
double phi=atan2(y,x); // [-pi,pi]

Перевод из полярных координат в декартовы:

double x=r*cos(phi);
double y=r*sin(phi);

Отрезок может быть определен через 2 точки. Прямая – через 2 точки `(x-a_x)/(b_x-a_x) = (y-a_y)/(b_y-a_y) = (z-a_z)/(b_z-a_z)` или уравнением `A x+B y+C=0` в 2D.

Окружность в 2D или сфера в 3D – через точку и радиус.

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

Векторное произведение определяет вектор, перпендикулярный обоим исходным векторам, длина которого численно равна площади параллелограмма, образованного исходными векторами.
`[a,b]=|{:(i,j,k),(a_x, a_y, a_z),(b_x,b_y,b_z):}|`.

Для 2D `z=|{:(a_x,a_y),(b_x,b_y):}|=a_x*b_y-a_y*b_x`. Знак `z` определяет, куда нужно сделать поворот `a`, чтобы он совпал с `b` – по или против часовой стрелки.

Модуль `1/6 * |{:(a_x, a_y, a_z),(b_x,b_y,b_z),(c_x,c_y,c_z):}|` дает объем пирамиды на векторах `a,b,c`

struct Point { 
  double x,y; 
  double len() const { return hypot(x,y); } // расстояние от начала координат
  double phi() const { return atan2(y,x); } // угол
  Point operator+(Point p) const { return {x+p.x,y+p.y}; } 
  Point operator-(Point p) const { return {x-p.x,y-p.y}; }
  double operator*(Point p) const { return x*p.x+y*p.y; } // скалярное произведение
  double operator^(Point p) const { return x*p.y-y*p.x; } // векторное произведение
  Point operator*(double a) const { return  {a*x,a*y};} // "масштабирование"
  Point turn(double a) const { double ca=cos(a),sa=sin(a); return {x*ca-y*sa,-x*sa+y*ca}; } // поворот
  Point turn() const { return {-y,x}; } // поворот на п/2 
  Point operator-() const { return {-x,-y}; } // поворот на п
};
inline Point operator*(double a, Point p) { return p*a; } // "масштабирование"

Отрезок: typedef pair<Point,Point> Segment;

Варианты представления прямой:

1. через коэффициенты уравнения прямой на плоскости: struct Line {double A,B,C; }; // `Ax+By+C=0`

Точку пересечения прямых можно найти, решая систему линейных уравнений

2. через две точки typedef pair<Point,Point> Line;