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
|
// 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); }
// 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;
}
|
