[algo](https://e-maxx.ru/algo/#:~:text=декомпозиция [TeX]-,Геометрия (23),-элементарные алгоритмы (10)

Геометрические примитивы

struct r {
    int x, y;
    r() {}
    r(int x, int y) : x(x), y(y) {}

		double len() { return hypot(x, y); }

		double angle() {
		    return atan2(y, x);
		}
};

r operator+(r a, r b) { return {a.x + b.x, a.y + b.y}; }
r operator-(r a, r b) { return {a.x - b.x, a.y - b.y}; }

int operator*(r a, r b) { return a.x * b.x + a.y * b.y; }
int operator^(r a, r b) { return a.x*b.y - b.x*a.y; }

istream& operator>>(istream &in, r &p) { 
    in >> p.x >> p.y;
    return in;
}

ostream& operator<<(ostream &out, r &p) { 
    out << p.x << " " << p.y << endl;
    return out;            
}

double angle(r a, r b) {
    return atan2(a ^ b, a * b);
}

r rot(r a, double alpha) {
	return {cos(alpha) * x - sin(alpha) * y, sin(alpha) * x + cos(alpha) * y};
}

struct segment {
    r p, q;
};

bool suppression(segment a, segment b){
	return ((a.p - b.p) ^ (b.p - b.q)) * ((a.q - b.p) ^ (b.q - b.p)) < 0;
}

const double EPS = 1e-9;

struct line {
		int a, b, c;
		double n = sqrt(a*a + b*b);

		line(int a, int b, int c) : a(a), b(b), c(c) {}

		line(r p, r q){
			a = p.y - q.y;
			b = q.x - p.x;
			c = -a*p.x - b*p.y;	
		}

		double dist(r p) {
				return abs(a * p.x + b * p.y + c) / n;
		}

		r norm() { return {a, b}; }

		r norm_unit() { return {a / n, b / n}; }

		r guide() { return {-b, a}; }
}

r projection(line l, r p) {
		return p + l.norm_unit() * l.dist(p);
}

double det (double a, double b, double c, double d) {
		return a * d - b * c;
}

bool intersect (line m, line n, r & res) {
		double zn = det (m.a, m.b, n.a, n.b);
		if (abs (zn) < EPS)
				return false;
		res.x = - det (m.c, m.b, n.c, n.b) / zn;
		res.y = - det (m.a, m.c, n.a, n.c) / zn;
		return true;
}
 
bool parallel (line m, line n) {
		return abs (det (m.a, m.b, n.a, n.b)) < EPS;
}
 
bool equivalent (line m, line n) {
		return abs (det (m.a, m.b, n.a, n.b)) < EPS
			&& abs (det (m.a, m.c, n.a, n.c)) < EPS
			&& abs (det (m.b, m.c, n.b, n.c)) < EPS;
}