1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
// Komplexe Zahlen als Punkte. Wenn immer möglich complex<ll>
// verwenden. Funktionen wie abs() geben dann aber ll zurück.
using pt = complex<double>;
constexpr double PIU = acos(-1.0l); // PIL < PI < PIU
constexpr double PIL = PIU-2e-19l;
// Winkel zwischen Punkt und x-Achse in [-PI, PI].
double angle(pt a) {return arg(a);}
// rotiert Punkt im Uhrzeigersinn um den Ursprung.
pt rotate(pt a, double theta) {return a * polar(1.0, theta);}
// Skalarprodukt.
auto dot(pt a, pt b) {return real(conj(a) * b);}
// abs()^2.(pre c++20)
auto norm(pt a) {return dot(a, a);}
// Kreuzprodukt, 0, falls kollinear.
auto cross(pt a, pt b) {return imag(conj(a) * b);}
auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);}
// 1 => c links von a->b
// 0 => a, b und c kolliniear
// -1 => c rechts von a->b
int ccw(pt a, pt b, pt c) {
auto orien = cross(b - a, c - a);
return (orien > EPS) - (orien < -EPS);
}
// Liegt d in der gleichen Ebene wie a, b, und c?
bool isCoplanar(pt a, pt b, pt c, pt d) {
return abs((b - a) * (c - a) * (d - a)) < EPS;
}
// charakterisiert winkel zwischen Vektoren u und v
pt uniqueAngle(pt u, pt v) {
pt tmp = v * conj(u);
ll g = abs(gcd(real(tmp), imag(tmp)));
return tmp / g;
}
|
