GCC Code Coverage Report

Directory: ./
File: tasks/pylaeva_s_convex_hull_bin/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 190 193 98.4%
Functions: 17 17 100.0%
Branches: 146 208 70.2%
Line Branch Exec Source
1 #include "pylaeva_s_convex_hull_bin/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <queue>
9 #include <utility>
10 #include <vector>
11
12 #include "pylaeva_s_convex_hull_bin/common/include/common.hpp"
13
14 namespace pylaeva_s_convex_hull_bin {
15
16 namespace {
17
18 int Cross(const Point &o, const Point &a, const Point &b) {
19
2/2
✓ Branch 0 taken 499 times.
✓ Branch 1 taken 533 times.
 1032 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
20 }
21
22 } // namespace
23
24
2/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
 20 PylaevaSConvexHullBinMPI::PylaevaSConvexHullBinMPI(const InType &in) : local_data_(in) {
25 SetTypeOfTask(GetStaticTypeOfTask());
26
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GetInput() = in;
27
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
28
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Comm_size(MPI_COMM_WORLD, &size_);
29
30
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank_ == 0) {
31
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 full_data_ = in;
32 }
33 20 }
34
35 20 bool PylaevaSConvexHullBinMPI::ValidationImpl() {
36
3/6
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 20 times.
 20 return GetInput().width > 0 && GetInput().height > 0 && !GetInput().pixels.empty() &&
37
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 GetInput().pixels.size() == static_cast<size_t>(GetInput().width) * static_cast<size_t>(GetInput().height);
38 }
39
40 20 bool PylaevaSConvexHullBinMPI::PreProcessingImpl() {
41 const uint8_t threshold = 128;
42
43
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank_ == 0) {
44 10 int total_pixels = full_data_.width * full_data_.height;
45
2/2
✓ Branch 0 taken 154000 times.
✓ Branch 1 taken 10 times.
 154010 for (int i = 0; i < total_pixels; ++i) {
46
2/2
✓ Branch 0 taken 578 times.
✓ Branch 1 taken 153422 times.
 154000 if (full_data_.pixels[i] > threshold) {
47 578 full_data_.pixels[i] = 255;
48 } else {
49 153422 full_data_.pixels[i] = 0;
50 }
51 }
52 }
53
54 20 ScatterDataAndDistributeWork();
55
56 20 return true;
57 }
58
59 20 void PylaevaSConvexHullBinMPI::ScatterDataAndDistributeWork() {
60 20 int width = 0;
61 20 int height = 0;
62
63
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank_ == 0) {
64 10 width = full_data_.width;
65 10 height = full_data_.height;
66 }
67
68 20 MPI_Bcast(&width, 1, MPI_INT, 0, MPI_COMM_WORLD);
69 20 MPI_Bcast(&height, 1, MPI_INT, 0, MPI_COMM_WORLD);
70
71 20 local_data_.width = width;
72 20 local_data_.height = height;
73
74 20 rows_per_proc_ = height / size_;
75 20 int remainder = height % size_;
76
77
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 start_row_ = (rank_ * rows_per_proc_) + std::min(rank_, remainder);
78
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 end_row_ = start_row_ + rows_per_proc_ + (rank_ < remainder ? 1 : 0);
79
80 20 std::vector<int> send_counts(size_, 0);
81
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<int> displs(size_, 0);
82
83
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank_ == 0) {
84
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 10 times.
 30 for (int i = 0; i < size_; ++i) {
85
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 int proc_start = (i * rows_per_proc_) + std::min(i, remainder);
86
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 int proc_end = proc_start + rows_per_proc_ + (i < remainder ? 1 : 0);
87 20 send_counts[i] = (proc_end - proc_start) * width;
88 20 displs[i] = proc_start * width;
89 }
90 }
91
92 20 int local_rows = end_row_ - start_row_;
93 20 size_t local_pixel_count = static_cast<size_t>(local_rows) * static_cast<size_t>(width);
94
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 local_data_.pixels.resize(local_pixel_count);
95
96
3/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
✓ Branch 3 taken 20 times.
✗ Branch 4 not taken.
 30 MPI_Scatterv(rank_ == 0 ? full_data_.pixels.data() : nullptr, send_counts.data(), displs.data(), MPI_UINT8_T,
97 local_data_.pixels.data(), static_cast<int>(local_pixel_count), MPI_UINT8_T, 0, MPI_COMM_WORLD);
98 20 }
99
100 20 bool PylaevaSConvexHullBinMPI::RunImpl() {
101 20 FindConnectedComponentsMpi();
102 20 ProcessComponentsAndComputeHulls();
103 20 GatherConvexHullsToRank0();
104 20 GetOutput() = local_data_;
105 20 return true;
106 }
107
108 20 void PylaevaSConvexHullBinMPI::GatherConvexHullsToRank0() {
109
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 20 std::vector<int> hull_counts(size_, 0);
110
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 int local_hull_count = static_cast<int>(local_data_.convex_hulls.size());
111
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 MPI_Gather(&local_hull_count, 1, MPI_INT, hull_counts.data(), 1, MPI_INT, 0, MPI_COMM_WORLD);
112
113
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank_ == 0) {
114
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<std::vector<Point>> rank0_hulls = local_data_.convex_hulls;
115 local_data_.convex_hulls.clear();
116
117
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int i = 1; i < size_; ++i) {
118
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 ReceiveHullsFromProcess(i, hull_counts[i]);
119 }
120
121
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 10 times.
 19 for (const auto &hull : rank0_hulls) {
122
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 local_data_.convex_hulls.push_back(hull);
123 }
124 10 } else {
125
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 SendHullsToRank0();
126 }
127 20 }
128
129 10 void PylaevaSConvexHullBinMPI::ReceiveHullsFromProcess(int source_rank, int hull_count) {
130
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 10 times.
 26 for (int j = 0; j < hull_count; ++j) {
131 16 int hull_size = 0;
132 16 MPI_Recv(&hull_size, 1, MPI_INT, source_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
133
134
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (hull_size <= 0) {
135 ✗ continue;
136 }
137
138 16 std::vector<Point> hull(hull_size);
139
1/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 16 std::vector<int> point_data(static_cast<size_t>(hull_size) * 2);
140
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Recv(point_data.data(), hull_size * 2, MPI_INT, source_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
141
142
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (int k = 0; k < hull_size; ++k) {
143 48 size_t base_idx = static_cast<size_t>(k) * 2;
144 48 hull[k].x = point_data[base_idx];
145 48 hull[k].y = point_data[base_idx + 1];
146 }
147
148
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 local_data_.convex_hulls.push_back(hull);
149 }
150 10 }
151
152 10 void PylaevaSConvexHullBinMPI::SendHullsToRank0() {
153
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 10 times.
 26 for (const auto &hull : local_data_.convex_hulls) {
154 16 int hull_size = static_cast<int>(hull.size());
155 16 MPI_Send(&hull_size, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
156
157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (hull_size <= 0) {
158 ✗ continue;
159 }
160
161 16 std::vector<int> point_data;
162
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 point_data.reserve(static_cast<size_t>(hull_size) * 2);
163
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 for (const auto &point : hull) {
164
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 point_data.push_back(point.x);
165
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 point_data.push_back(point.y);
166 }
167
168
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 MPI_Send(point_data.data(), hull_size * 2, MPI_INT, 0, 0, MPI_COMM_WORLD);
169 }
170 10 }
171
172
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 void PylaevaSConvexHullBinMPI::ProcessComponentsAndComputeHulls() {
173 local_data_.convex_hulls.clear();
174
175
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 20 times.
 45 for (const auto &component : local_data_.components) {
176
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 8 times.
 25 if (component.size() >= 3) {
177 34 local_data_.convex_hulls.push_back(GrahamScan(component));
178
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 } else if (!component.empty()) {
179 8 local_data_.convex_hulls.push_back(component);
180 }
181 }
182 20 }
183
184 20 void PylaevaSConvexHullBinMPI::FindConnectedComponentsMpi() {
185 20 int width = local_data_.width;
186 20 int height = local_data_.height;
187 20 int local_rows = end_row_ - start_row_;
188
189 20 int extended_start_row = std::max(0, start_row_ - 1);
190 20 int extended_end_row = std::min(height, end_row_ + 1);
191 20 int extended_local_rows = extended_end_row - extended_start_row;
192
193 20 std::vector<uint8_t> extended_pixels(static_cast<size_t>(extended_local_rows) * width);
194
195
2/2
✓ Branch 0 taken 1100 times.
✓ Branch 1 taken 20 times.
 1120 for (int row = 0; row < local_rows; ++row) {
196 1100 int global_row = start_row_ + row;
197 1100 int ext_row = global_row - extended_start_row;
198
2/2
✓ Branch 0 taken 154000 times.
✓ Branch 1 taken 1100 times.
 155100 for (int col = 0; col < width; ++col) {
199 154000 size_t local_idx = (static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
200 154000 size_t ext_idx = (static_cast<size_t>(ext_row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
201 154000 extended_pixels[ext_idx] = local_data_.pixels[local_idx];
202 }
203 }
204
205
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ExchangeBoundaryRows(width, local_rows, extended_start_row, extended_local_rows, extended_pixels);
206
207
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<bool> visited_extended(static_cast<size_t>(extended_local_rows) * width, false);
208 20 std::vector<std::vector<Point>> all_components;
209
210
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ProcessExtendedRegion(width, extended_start_row, extended_local_rows, extended_pixels, visited_extended,
211 all_components);
212
213
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 FilterLocalComponents(all_components);
214 40 }
215
216 20 void PylaevaSConvexHullBinMPI::ExchangeBoundaryRows(int width, int local_rows, int extended_start_row,
217 int extended_local_rows,
218 std::vector<uint8_t> &extended_pixels) const {
219
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (start_row_ > 0) {
220 10 int prev_rank = rank_ - 1;
221 int top_row_in_extended = 0;
222 10 MPI_Send(&extended_pixels[static_cast<size_t>(top_row_in_extended) * static_cast<size_t>(width)], width,
223 MPI_UINT8_T, prev_rank, 0, MPI_COMM_WORLD);
224 }
225
226
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (end_row_ < local_data_.height) {
227 10 int next_rank = rank_ + 1;
228
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (next_rank < size_) {
229 10 int bottom_row_in_extended = extended_local_rows - 1;
230 10 MPI_Recv(&extended_pixels[static_cast<size_t>(bottom_row_in_extended) * static_cast<size_t>(width)], width,
231 MPI_UINT8_T, next_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
232 }
233 }
234
235
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (end_row_ < local_data_.height) {
236 10 int next_rank = rank_ + 1;
237
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (next_rank < size_) {
238 10 int bottom_local_row = local_rows - 1;
239 10 int bottom_row_in_extended = (start_row_ + bottom_local_row) - extended_start_row;
240 10 MPI_Send(&extended_pixels[static_cast<size_t>(bottom_row_in_extended) * static_cast<size_t>(width)], width,
241 MPI_UINT8_T, next_rank, 1, MPI_COMM_WORLD);
242 }
243 }
244
245
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (start_row_ > 0) {
246 10 int prev_rank = rank_ - 1;
247 int top_row_in_extended = 0;
248 10 MPI_Recv(&extended_pixels[static_cast<size_t>(top_row_in_extended) * static_cast<size_t>(width)], width,
249 MPI_UINT8_T, prev_rank, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
250 }
251 20 }
252
253 20 void PylaevaSConvexHullBinMPI::ProcessExtendedRegion(int width, int extended_start_row, int extended_local_rows,
254 const std::vector<uint8_t> &extended_pixels,
255 std::vector<bool> &visited_extended,
256 std::vector<std::vector<Point>> &all_components) {
257
2/2
✓ Branch 0 taken 1120 times.
✓ Branch 1 taken 20 times.
 1140 for (int ext_row = 0; ext_row < extended_local_rows; ++ext_row) {
258 1120 int global_row = extended_start_row + ext_row;
259
2/2
✓ Branch 0 taken 156200 times.
✓ Branch 1 taken 1120 times.
 157320 for (int col = 0; col < width; ++col) {
260
2/2
✓ Branch 0 taken 619 times.
✓ Branch 1 taken 155581 times.
 156200 size_t ext_idx = (static_cast<size_t>(ext_row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
261
262
4/4
✓ Branch 0 taken 619 times.
✓ Branch 1 taken 155581 times.
✓ Branch 2 taken 25 times.
✓ Branch 3 taken 594 times.
 156819 if (extended_pixels[ext_idx] == 255 && !visited_extended[ext_idx]) {
263
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 std::vector<Point> component;
264 std::queue<Point> q;
265 q.emplace(col, global_row);
266 visited_extended[ext_idx] = true;
267
268
2/2
✓ Branch 0 taken 619 times.
✓ Branch 1 taken 25 times.
 644 while (!q.empty()) {
269 619 Point p = q.front();
270 q.pop();
271 component.push_back(p);
272
273
1/2
✓ Branch 1 taken 619 times.
✗ Branch 2 not taken.
 619 ProcessExtendedNeighbors(p, width, extended_start_row, extended_local_rows, extended_pixels, visited_extended,
274 q);
275 }
276
277
1/2
✓ Branch 0 taken 25 times.
✗ Branch 1 not taken.
 25 if (!component.empty()) {
278
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 all_components.push_back(component);
279 }
280 }
281 }
282 }
283 20 }
284
285 619 void PylaevaSConvexHullBinMPI::ProcessExtendedNeighbors(const Point &p, int width, int extended_start_row,
286 int extended_local_rows,
287 const std::vector<uint8_t> &extended_pixels,
288 std::vector<bool> &visited_extended, std::queue<Point> &q) {
289 619 const std::vector<std::pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
290
291
2/2
✓ Branch 0 taken 2476 times.
✓ Branch 1 taken 619 times.
 3095 for (const auto &dir : directions) {
292 2476 int nx = p.x + dir.first;
293 2476 int ny = p.y + dir.second;
294
295 2476 int ext_row = ny - extended_start_row;
296
6/6
✓ Branch 0 taken 2470 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 2467 times.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 2417 times.
✓ Branch 5 taken 50 times.
 2476 if (nx >= 0 && nx < width && ext_row >= 0 && ext_row < extended_local_rows) {
297
2/2
✓ Branch 0 taken 1854 times.
✓ Branch 1 taken 563 times.
 2417 size_t ext_idx = (static_cast<size_t>(ext_row) * static_cast<size_t>(width)) + static_cast<size_t>(nx);
298
299
4/4
✓ Branch 0 taken 1854 times.
✓ Branch 1 taken 563 times.
✓ Branch 2 taken 594 times.
✓ Branch 3 taken 1260 times.
 2417 if (extended_pixels[ext_idx] == 255 && !visited_extended[ext_idx]) {
300 visited_extended[ext_idx] = true;
301 q.emplace(nx, ny);
302 }
303 }
304 }
305 619 }
306
307
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 void PylaevaSConvexHullBinMPI::FilterLocalComponents(const std::vector<std::vector<Point>> &all_components) {
308 local_data_.components.clear();
309
310
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 20 times.
 45 for (const auto &component : all_components) {
311 bool belongs_to_local = false;
312
1/2
✓ Branch 0 taken 37 times.
✗ Branch 1 not taken.
 37 for (const auto &point : component) {
313
3/4
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 25 times.
 37 if (point.y >= start_row_ && point.y < end_row_) {
314 belongs_to_local = true;
315 break;
316 }
317 }
318
319
1/2
✓ Branch 0 taken 25 times.
✗ Branch 1 not taken.
 25 if (belongs_to_local) {
320 25 local_data_.components.push_back(component);
321 }
322 }
323 20 }
324
325 20 bool PylaevaSConvexHullBinMPI::PostProcessingImpl() {
326 20 return true;
327 }
328
329
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 17 std::vector<Point> PylaevaSConvexHullBinMPI::GrahamScan(const std::vector<Point> &points) {
330
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
 17 if (points.size() <= 3) {
331 ✗ return points;
332 }
333
334 17 std::vector<Point> pts = points;
335 17 int n = static_cast<int>(pts.size());
336
337 int min_idx = 0;
338
2/2
✓ Branch 0 taken 594 times.
✓ Branch 1 taken 17 times.
 611 for (int i = 1; i < n; ++i) {
339
4/6
✓ Branch 0 taken 594 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 62 times.
✓ Branch 3 taken 532 times.
✓ Branch 4 taken 62 times.
✗ Branch 5 not taken.
 594 if (pts[i].y < pts[min_idx].y || (pts[i].y == pts[min_idx].y && pts[i].x < pts[min_idx].x)) {
340 min_idx = i;
341 }
342 }
343 17 std::swap(pts[0], pts[min_idx]);
344
345 17 Point pivot = pts[0];
346 3789 std::sort(pts.begin() + 1, pts.end(), [&pivot](const Point &a, const Point &b) {
347 3772 int orient = Cross(pivot, a, b);
348
2/2
✓ Branch 0 taken 662 times.
✓ Branch 1 taken 3110 times.
 3772 if (orient == 0) {
349 662 return ((a.x - pivot.x) * (a.x - pivot.x)) + ((a.y - pivot.y) * (a.y - pivot.y)) <
350 662 ((b.x - pivot.x) * (b.x - pivot.x)) + ((b.y - pivot.y) * (b.y - pivot.y));
351 }
352 3110 return orient > 0;
353 });
354
355
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 std::vector<Point> hull;
356
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 hull.reserve(pts.size());
357
2/2
✓ Branch 0 taken 611 times.
✓ Branch 1 taken 17 times.
 628 for (int i = 0; i < n; ++i) {
358
4/4
✓ Branch 0 taken 1032 times.
✓ Branch 1 taken 112 times.
✓ Branch 2 taken 499 times.
✓ Branch 3 taken 533 times.
 1144 while (hull.size() >= 2 && Cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
359 hull.pop_back();
360 }
361
1/2
✓ Branch 0 taken 611 times.
✗ Branch 1 not taken.
 611 hull.push_back(pts[i]);
362 }
363
364 return hull;
365 }
366
367 } // namespace pylaeva_s_convex_hull_bin
368