GCC Code Coverage Report

Directory: ./
File: tasks/perepelkin_i_convex_hull_graham_scan/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 166 174 95.4%
Functions: 19 22 86.4%
Branches: 130 236 55.1%
Line Branch Exec Source
1 #include "perepelkin_i_convex_hull_graham_scan/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <tbb/blocked_range.h>
5 #include <tbb/global_control.h>
6 #include <tbb/parallel_invoke.h>
7 #include <tbb/parallel_reduce.h>
8 #include <tbb/parallel_sort.h>
9
10 #include <algorithm>
11 #include <cmath>
12 #include <cstddef>
13 #include <utility>
14 #include <vector>
15
16 #include "perepelkin_i_convex_hull_graham_scan/common/include/common.hpp"
17 #include "util/include/util.hpp"
18
19 namespace perepelkin_i_convex_hull_graham_scan {
20
21
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 PerepelkinIConvexHullGrahamScanALL::PerepelkinIConvexHullGrahamScanALL(const InType &in) {
22
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Comm_rank(MPI_COMM_WORLD, &proc_rank_);
23
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 MPI_Comm_size(MPI_COMM_WORLD, &proc_num_);
24
25 SetTypeOfTask(GetStaticTypeOfTask());
26
27
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (proc_rank_ == 0) {
28
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
29 }
30
31 24 GetOutput() = std::vector<std::pair<double, double>>();
32 24 }
33
34 24 bool PerepelkinIConvexHullGrahamScanALL::ValidationImpl() {
35 24 return GetOutput().empty();
36 }
37
38 24 bool PerepelkinIConvexHullGrahamScanALL::PreProcessingImpl() {
39 24 return true;
40 }
41
42 24 bool PerepelkinIConvexHullGrahamScanALL::RunImpl() {
43 24 MPI_Type_contiguous(2, MPI_DOUBLE, &MPI_POINT_);
44 24 MPI_Type_commit(&MPI_POINT_);
45
46 // [1] Broadcast original and padded sizes
47 24 size_t original_size = 0;
48 24 size_t padded_size = 0;
49 24 BcastSizes(original_size, padded_size);
50
51 // Handle edge cases
52
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 20 times.
 24 if (original_size <= 1) {
53
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (proc_rank_ == 0) {
54 2 GetOutput() = GetInput();
55 }
56 4 BcastOutput();
57 4 MPI_Type_free(&MPI_POINT_);
58 4 return true;
59 }
60
61 20 tbb::global_control gc(tbb::global_control::max_allowed_parallelism, ppc::util::GetNumThreads());
62
63 // [2] Distribute data
64 20 std::vector<std::pair<double, double>> local_data;
65
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 DistributeData(original_size, padded_size, local_data);
66
67 // [3] Local find pivot
68
69 // Remove fake points
70
2/4
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 58 auto result = std::ranges::remove_if(local_data, [](const auto &p) { return p.first > 1e17; });
71 local_data.erase(result.begin(), result.end());
72
73 20 std::pair<double, double> local_pivot = {1e18, 1e18};
74
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 FindPivotParallel(local_data, local_pivot);
75
76 // [4] Find global pivot
77 20 std::pair<double, double> global_pivot{};
78
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 FindGlobalPivot(local_data, local_pivot, global_pivot);
79
80 // [5] Local parallel sorting
81 ParallelSort(local_data, global_pivot);
82
83 // [6] Gather sorted blocks
84 ✗ std::vector<int> real_counts(proc_num_);
85
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<int> real_displs(proc_num_);
86 20 std::vector<std::pair<double, double>> gathered;
87
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GatherSortedBlocks(local_data, real_counts, real_displs, gathered);
88
89 // [7] Merge sorted blocks (parallel)
90 20 std::vector<std::pair<double, double>> sorted;
91
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
92
1/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 sorted = MergeSortedBlocksParallel(gathered, real_counts, real_displs, global_pivot);
93 }
94
95 // [8] Sequential hull construction
96
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
97 10 std::vector<std::pair<double, double>> hull;
98
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 HullConstruction(hull, sorted, global_pivot);
99 GetOutput() = std::move(hull);
100 }
101
102 // [9] Bcast output to all processes
103
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 BcastOutput();
104
105
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Type_free(&MPI_POINT_);
106 return true;
107 }
108
109 //
110 // Transfer data
111 //
112 24 void PerepelkinIConvexHullGrahamScanALL::BcastSizes(size_t &original_size, size_t &padded_size) {
113
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (proc_rank_ == 0) {
114 12 original_size = GetInput().size();
115 12 const size_t remainder = original_size % proc_num_;
116
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 5 times.
 12 padded_size = original_size + (remainder == 0 ? 0 : (proc_num_ - remainder));
117 }
118
119 24 MPI_Bcast(&original_size, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
120 24 MPI_Bcast(&padded_size, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
121 24 }
122
123 24 void PerepelkinIConvexHullGrahamScanALL::BcastOutput() {
124 24 size_t size = 0;
125
126
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 24 if (proc_rank_ == 0) {
127 12 size = GetOutput().size();
128 }
129
130 24 MPI_Bcast(&size, 1, MPI_UNSIGNED_LONG_LONG, 0, MPI_COMM_WORLD);
131
132 24 GetOutput().resize(size);
133
134
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
 24 if (size > 0) {
135 22 MPI_Bcast(GetOutput().data(), static_cast<int>(size), MPI_POINT_, 0, MPI_COMM_WORLD);
136 }
137 24 }
138
139 20 void PerepelkinIConvexHullGrahamScanALL::DistributeData(const size_t &original_size, const size_t &padded_size,
140 std::vector<std::pair<double, double>> &local_data) {
141 20 std::vector<std::pair<double, double>> padded_input;
142
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
143
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 padded_input = GetInput();
144
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
 10 if (padded_size > original_size) {
145
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 padded_input.resize(padded_size, std::make_pair(1e18, 1e18));
146 }
147 }
148
149 20 std::vector<int> counts;
150 20 std::vector<int> displs;
151 20 const int base_size = static_cast<int>(padded_size / proc_num_);
152
153
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 counts.resize(proc_num_);
154
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 displs.resize(proc_num_);
155
156
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 for (int i = 0, offset = 0; i < proc_num_; i++) {
157 40 counts[i] = base_size;
158 40 displs[i] = offset;
159 40 offset += base_size;
160 }
161
162
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 const int local_size = counts[proc_rank_];
163
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 local_data.resize(local_size);
164
165
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Scatterv(padded_input.data(), counts.data(), displs.data(), MPI_POINT_, local_data.data(), local_size, MPI_POINT_,
166 0, MPI_COMM_WORLD);
167 20 }
168
169 20 void PerepelkinIConvexHullGrahamScanALL::FindGlobalPivot(std::vector<std::pair<double, double>> &local_data,
170 const std::pair<double, double> &local_pivot,
171 std::pair<double, double> &global_pivot) {
172 20 std::vector<std::pair<double, double>> pivots;
173
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
174
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 pivots.resize(proc_num_);
175 }
176
177
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Gather(&local_pivot, 1, MPI_POINT_, pivots.data(), 1, MPI_POINT_, 0, MPI_COMM_WORLD);
178
179 // [4.2] Find global pivot
180
181
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
182 global_pivot = pivots[0];
183
184
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int i = 1; i < proc_num_; i++) {
185
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 3 times.
 10 if (IsBetterPivot(pivots[i], global_pivot)) {
186 global_pivot = pivots[i];
187 }
188 }
189 }
190
191
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Bcast(&global_pivot, 1, MPI_POINT_, 0, MPI_COMM_WORLD);
192
193 // Remove global pivot
194
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 8 times.
 20 int owner_rank = -1;
195 if (local_pivot == global_pivot) {
196 10 owner_rank = proc_rank_;
197 }
198 20 int pivot_rank = -1;
199
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Allreduce(&owner_rank, &pivot_rank, 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
200
201
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == pivot_rank) {
202 auto it = std::ranges::find(local_data, global_pivot);
203
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (it != local_data.end()) {
204 local_data.erase(it);
205 }
206 }
207 20 }
208
209 20 void PerepelkinIConvexHullGrahamScanALL::GatherSortedBlocks(std::vector<std::pair<double, double>> &local_data,
210 std::vector<int> &real_counts,
211 std::vector<int> &real_displs,
212 std::vector<std::pair<double, double>> &gathered) {
213 20 int local_size = static_cast<int>(local_data.size());
214
215 20 MPI_Gather(&local_size, 1, MPI_INT, real_counts.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
216
217
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (proc_rank_ == 0) {
218 int offset = 0;
219
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 for (int i = 0; i < proc_num_; i++) {
220 20 real_displs[i] = offset;
221 20 offset += real_counts[i];
222 }
223 10 gathered.resize(offset);
224 }
225
226 20 MPI_Gatherv(local_data.data(), local_size, MPI_POINT_, gathered.data(), real_counts.data(), real_displs.data(),
227 MPI_POINT_, 0, MPI_COMM_WORLD);
228 20 }
229
230 //
231 // Merge blocks
232 //
233 10 std::vector<std::pair<double, double>> PerepelkinIConvexHullGrahamScanALL::MergeSortedBlocksParallel(
234 const std::vector<std::pair<double, double>> &gathered, const std::vector<int> &counts,
235 const std::vector<int> &displs, const std::pair<double, double> &pivot) {
236 10 std::vector<std::vector<std::pair<double, double>>> blocks;
237
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 blocks.reserve(proc_num_);
238
239
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 for (int i = 0; i < proc_num_; i++) {
240
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 1 times.
 20 if (counts[i] > 0) {
241
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 blocks.emplace_back(gathered.begin() + displs[i], gathered.begin() + displs[i] + counts[i]);
242 } else {
243
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 blocks.emplace_back();
244 }
245 }
246
247
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 20 return MergeBlocksRange(blocks, 0, static_cast<int>(blocks.size()), pivot);
248 10 }
249
250 30 std::vector<std::pair<double, double>> PerepelkinIConvexHullGrahamScanALL::MergeBlocksRange(
251 const std::vector<std::vector<std::pair<double, double>>> &blocks, int left, int right,
252 const std::pair<double, double> &pivot) {
253
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (right - left <= 0) {
254 ✗ return {};
255 }
256
257
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 if (right - left == 1) {
258 20 return blocks[left];
259 }
260
261 10 const int mid = left + ((right - left) / 2);
262
263 10 std::vector<std::pair<double, double>> merged_left;
264 10 std::vector<std::pair<double, double>> merged_right;
265
266 10 tbb::parallel_invoke([&]() { merged_left = MergeBlocksRange(blocks, left, mid, pivot); },
267
1/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 [&]() { merged_right = MergeBlocksRange(blocks, mid, right, pivot); });
268
269
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 return MergeTwoBlocks(merged_left, merged_right, pivot);
270 }
271
272 10 std::vector<std::pair<double, double>> PerepelkinIConvexHullGrahamScanALL::MergeTwoBlocks(
273 const std::vector<std::pair<double, double>> &left, const std::vector<std::pair<double, double>> &right,
274 const std::pair<double, double> &pivot) {
275
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<std::pair<double, double>> result;
276
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 result.reserve(left.size() + right.size());
277
278 size_t i = 0;
279 size_t j = 0;
280
281
4/4
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 26 times.
 36 while (i < left.size() && j < right.size()) {
282
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 10 times.
 26 if (AngleCmp(left[i], right[j], pivot)) {
283 result.push_back(left[i]);
284 16 i++;
285 } else {
286 result.push_back(right[j]);
287 10 j++;
288 }
289 }
290
291
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 10 times.
 17 while (i < left.size()) {
292 result.push_back(left[i]);
293 7 i++;
294 }
295
296
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 10 times.
 19 while (j < right.size()) {
297 result.push_back(right[j]);
298 9 j++;
299 }
300
301 10 return result;
302 }
303
304 //
305 // Threads parallelization
306 //
307
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 void PerepelkinIConvexHullGrahamScanALL::FindPivotParallel(const std::vector<std::pair<double, double>> &pts,
308 std::pair<double, double> &local_pivot) {
309
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (pts.empty()) {
310 ✗ return;
311 }
312
313 auto better = [&](size_t a, size_t b) {
314
4/8
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 15 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 4 times.
✓ Branch 7 taken 4 times.
 23 if (pts[b].second < pts[a].second || (pts[b].second == pts[a].second && pts[b].first < pts[a].first)) {
315 return b;
316 }
317 return a;
318 20 };
319
320 40 size_t pivot_idx = tbb::parallel_reduce(tbb::blocked_range<size_t>(1, pts.size()), static_cast<size_t>(0),
321 32 [&](const tbb::blocked_range<size_t> &r, size_t local_idx) {
322
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 for (size_t i = r.begin(); i != r.end(); i++) {
323
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 9 times.
 32 local_idx = better(local_idx, i);
324 }
325 32 return local_idx;
326
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 20 }, [&](size_t a, size_t b) { return better(a, b); });
327
328 local_pivot = pts[pivot_idx];
329 }
330
331 ✗ void PerepelkinIConvexHullGrahamScanALL::ParallelSort(std::vector<std::pair<double, double>> &data,
332 const std::pair<double, double> &pivot) {
333
6/46
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✓ Branch 20 taken 5 times.
✓ Branch 21 taken 14 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✓ Branch 38 taken 9 times.
✓ Branch 39 taken 14 times.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✓ Branch 44 taken 20 times.
✗ Branch 45 not taken.
✓ Branch 47 taken 20 times.
✗ Branch 48 not taken.
 62 tbb::parallel_sort(data.begin(), data.end(), [&](const auto &a, const auto &b) { return AngleCmp(a, b, pivot); });
334 ✗ }
335
336 //
337 // Sequential
338 //
339
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 void PerepelkinIConvexHullGrahamScanALL::HullConstruction(std::vector<std::pair<double, double>> &hull,
340 const std::vector<std::pair<double, double>> &pts,
341 const std::pair<double, double> &pivot) {
342 hull.clear();
343 hull.push_back(pivot);
344
345
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (pts.empty()) {
346 return;
347 }
348
349 hull.push_back(pts[0]);
350
351
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 10 times.
 42 for (size_t i = 1; i < pts.size(); i++) {
352
4/4
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 26 times.
 84 while (hull.size() >= 2 && Orientation(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0) {
353 hull.pop_back();
354 }
355 hull.push_back(pts[i]);
356 }
357 }
358
359 //
360 // Helpers
361 //
362 ✗ bool PerepelkinIConvexHullGrahamScanALL::IsBetterPivot(const std::pair<double, double> &a,
363 const std::pair<double, double> &b) {
364
6/12
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 7 times.
✓ Branch 7 taken 3 times.
✓ Branch 8 taken 2 times.
✓ Branch 9 taken 5 times.
✓ Branch 10 taken 1 times.
✓ Branch 11 taken 1 times.
 10 return (a.second < b.second) || (a.second == b.second && a.first < b.first);
365 }
366
367 ✗ double PerepelkinIConvexHullGrahamScanALL::Orientation(const std::pair<double, double> &p,
368 const std::pair<double, double> &q,
369 const std::pair<double, double> &r) {
370
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 36 times.
 42 double val = ((q.first - p.first) * (r.second - p.second)) - ((q.second - p.second) * (r.first - p.first));
371
372
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 36 times.
 42 if (std::abs(val) < 1e-9) {
373 ✗ return 0.0;
374 }
375
376 return val;
377 }
378
379 68 bool PerepelkinIConvexHullGrahamScanALL::AngleCmp(const std::pair<double, double> &a,
380 const std::pair<double, double> &b,
381 const std::pair<double, double> &pivot) {
382 68 double dx1 = a.first - pivot.first;
383 68 double dy1 = a.second - pivot.second;
384 68 double dx2 = b.first - pivot.first;
385 68 double dy2 = b.second - pivot.second;
386
387
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 53 times.
 68 double cross = (dx1 * dy2) - (dy1 * dx2);
388
389
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 53 times.
 68 if (std::abs(cross) < 1e-9) {
390 15 double dist1 = (dx1 * dx1) + (dy1 * dy1);
391 15 double dist2 = (dx2 * dx2) + (dy2 * dy2);
392 15 return dist1 < dist2;
393 }
394
395 53 return cross > 0;
396 }
397
398 24 bool PerepelkinIConvexHullGrahamScanALL::PostProcessingImpl() {
399 24 return true;
400 }
401
402 } // namespace perepelkin_i_convex_hull_graham_scan
403