GCC Code Coverage Report

Directory: ./
File: tasks/perepelkin_i_convex_hull_graham_scan/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 36 38 94.7%
Functions: 6 7 85.7%
Branches: 30 60 50.0%
Line Branch Exec Source
1 #include "perepelkin_i_convex_hull_graham_scan/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <utility>
7 #include <vector>
8
9 #include "perepelkin_i_convex_hull_graham_scan/common/include/common.hpp"
10
11 namespace perepelkin_i_convex_hull_graham_scan {
12
13
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 PerepelkinIConvexHullGrahamScanSEQ::PerepelkinIConvexHullGrahamScanSEQ(const InType &in) {
14 SetTypeOfTask(GetStaticTypeOfTask());
15
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
16 96 GetOutput() = std::vector<std::pair<double, double>>();
17 96 }
18
19 96 bool PerepelkinIConvexHullGrahamScanSEQ::ValidationImpl() {
20 96 return GetOutput().empty();
21 }
22
23 96 bool PerepelkinIConvexHullGrahamScanSEQ::PreProcessingImpl() {
24 96 return true;
25 }
26
27
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 bool PerepelkinIConvexHullGrahamScanSEQ::RunImpl() {
28 const auto &data = GetInput();
29
30
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 80 times.
 96 if (data.size() < 2) {
31 16 GetOutput() = data;
32 16 return true;
33 }
34
35 80 std::vector<std::pair<double, double>> pts = data;
36
37 // Find pivot: lowest y, then lowest x
38 auto pivot_it = std::ranges::min_element(pts, [](const auto &a, const auto &b) {
39
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 272 times.
 336 if (a.second == b.second) {
40 64 return a.first < b.first;
41 }
42 272 return a.second < b.second;
43 });
44 std::pair<double, double> pivot = *pivot_it;
45 pts.erase(pivot_it);
46
47 // Sort remaining points by polar angle around pivot (counter-clockwise)
48 std::ranges::sort(pts, [&](const std::pair<double, double> &a, const std::pair<double, double> &b) {
49
4/24
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 184 times.
✓ Branch 5 taken 216 times.
✗ 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 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 40 times.
✓ Branch 23 taken 216 times.
 656 return AngleCmp(a, b, pivot);
50 });
51
52 // Build hull
53
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<std::pair<double, double>> hull;
54
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 hull.reserve(pts.size() + 1);
55 hull.push_back(pivot);
56 hull.push_back(pts[0]);
57
58
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 80 times.
 336 for (size_t i = 1; i < pts.size(); i++) {
59
4/4
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 80 times.
✓ Branch 3 taken 208 times.
 672 while (hull.size() >= 2 && Orientation(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0) {
60 hull.pop_back();
61 }
62 hull.push_back(pts[i]);
63 }
64
65 GetOutput() = std::move(hull);
66 return true;
67 }
68
69 ✗ double PerepelkinIConvexHullGrahamScanSEQ::Orientation(const std::pair<double, double> &p,
70 const std::pair<double, double> &q,
71 const std::pair<double, double> &r) {
72
4/8
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 48 times.
✓ Branch 5 taken 288 times.
✓ Branch 6 taken 48 times.
✓ Branch 7 taken 288 times.
 672 double val = ((q.first - p.first) * (r.second - p.second)) - ((q.second - p.second) * (r.first - p.first));
73
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
✓ Branch 3 taken 288 times.
 336 if (std::abs(val) < 1e-9) {
74 ✗ return 0.0;
75 }
76 return val;
77 }
78
79 656 bool PerepelkinIConvexHullGrahamScanSEQ::AngleCmp(const std::pair<double, double> &a,
80 const std::pair<double, double> &b,
81 const std::pair<double, double> &pivot) {
82 656 double dx1 = a.first - pivot.first;
83 656 double dy1 = a.second - pivot.second;
84 656 double dx2 = b.first - pivot.first;
85 656 double dy2 = b.second - pivot.second;
86
87
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 512 times.
 656 double cross = (dx1 * dy2) - (dy1 * dx2);
88
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 512 times.
 656 if (std::abs(cross) < 1e-9) {
89 144 double dist1 = (dx1 * dx1) + (dy1 * dy1);
90 144 double dist2 = (dx2 * dx2) + (dy2 * dy2);
91 144 return dist1 < dist2;
92 }
93 512 return cross > 0;
94 }
95
96 96 bool PerepelkinIConvexHullGrahamScanSEQ::PostProcessingImpl() {
97 96 return true;
98 }
99
100 } // namespace perepelkin_i_convex_hull_graham_scan
101