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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
#include "../util.h"
constexpr double EPS = 1e-6;
#define ll double
double gcd(double x, double /**/) {return x;} //hacky
#include <geometry/formulas.cpp>
#undef ll
ll sgn(double x) {
return (x > EPS) - (x < -EPS);
}
#include <geometry/triangle.cpp>
#include "../geometry.h"
// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d
double distToLine(pt a, pt b, pt p) {
return abs(cross(p - a, b - a)) / abs(b - a);
}
void test_centroid(ll range) {
int queries = 0;
for (int tries = 0; tries < 1'000'000; tries++) {
auto [a, b, c] = Random::triangle(range);
pt center = centroid(a, b, c);
if (distToLine(2.0*a, c+b, 2.0*center) > 1e-6) cerr << "error: 1" << FAIL;
if (distToLine(2.0*b, c+a, 2.0*center) > 1e-6) cerr << "error: 2" << FAIL;
if (distToLine(2.0*c, a+b, 2.0*center) > 1e-6) cerr << "error: 3" << FAIL;
queries++;
}
cerr << "tested centroid: " << queries << endl;
}
void test_area(ll range) {
int queries = 0;
for (int tries = 0; tries < 1'000'000; tries++) {
auto [a, b, c] = Random::triangle(range);
auto gotA = 2*area(a, b, c);
auto gotB = 2*area(abs(a-b), abs(b-c), abs(c-a));
auto expected = llround(gotA);
if (float_error(gotA, expected) > 1e-6) cerr << "error: 1" << FAIL;
if (float_error(gotB, expected) > 1e-3) cerr << "error: 2" << FAIL;
queries++;
}
cerr << "tested area: " << queries << endl;
}
void test_inCenter(ll range) {
int queries = 0;
for (int tries = 0; tries < 1'000'000; tries++) {
auto [a, b, c] = Random::triangle(range);
pt center = inCenter(a, b, c);
double da = distToLine(a, b, center);
double db = distToLine(b, c, center);
double dc = distToLine(c, a, center);
double avg = (da + db + dc) / 3.0;
if (float_error(da, avg) > 1e-6) cerr << "error: 1" << FAIL;
if (float_error(db, avg) > 1e-6) cerr << "error: 2" << FAIL;
if (float_error(dc, avg) > 1e-6) cerr << "error: 3" << FAIL;
queries++;
}
cerr << "tested inCenter: " << queries << endl;
}
void test_circumCenter(ll range) {
int queries = 0;
for (int tries = 0; tries < 1'000'000; tries++) {
auto [a, b, c] = Random::triangle(range);
pt center = circumCenter(a, b, c);
double da = abs(center - a);
double db = abs(center - b);
double dc = abs(center - c);
double avg = (da + db + dc) / 3.0;
if (float_error(da, avg) > 1e-6) cerr << "error: 1" << FAIL;
if (float_error(db, avg) > 1e-6) cerr << "error: 2" << FAIL;
if (float_error(dc, avg) > 1e-6) cerr << "error: 3" << FAIL;
queries++;
}
cerr << "tested circumCenter: " << queries << endl;
}
void test_insideOutCenter(ll range) {
int queries = 0;
for (int tries = 0; tries < 1'000'000; tries++) {
auto [a, b, c] = Random::triangle(range);
pt p = Random::integerPoint(range);
pt center = circumCenter(a, b, c);
double da = abs(center - a);
double db = abs(center - b);
double dc = abs(center - c);
double dp = abs(center - p);
double avg = (da + db + dc) / 3.0;
int expected = dp < avg ? 1 : -1;
if (float_error(dp, avg) < 1e-9) expected = 0;
if (insideOutCenter(a, b, c, p) != expected) cerr << "error" << FAIL;
queries++;
}
cerr << "tested insideOutCenter: " << queries << endl;
}
void test_similar(ll range) {
int queries = 0;
for (int tries = 0; tries < 1'000'000; tries++) {
auto [a, b, c] = Random::triangle(sqrt(range));
pt rot = Random::integerPoint(sqrt(range));
pt add = Random::integerPoint(range);
pt d = rot * a + add;
pt e = rot * b + add;
pt f = rot * c + add;
if (!similar(a, b, c, d, e, f)) cerr << "error" << FAIL;
queries++;
}
cerr << "tested similar: " << queries << endl;
}
int main() {
test_centroid(100);
test_centroid(1'000'000'000);
test_area(100);
test_area(1'000'000'000);
test_inCenter(100);
test_inCenter(1'000'000'000);
test_circumCenter(100);
test_circumCenter(1'000'000'000);
test_insideOutCenter(100);
test_insideOutCenter(1'000'000'000);
test_similar(100);
test_similar(1'000'000'000);
}
|
