GCC Code Coverage Report

Directory: ./
File: tasks/makovskiy_i_graham_hull/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 42 42 100.0%
Functions: 9 9 100.0%
Branches: 37 50 74.0%
Line Branch Exec Source
1 #include "makovskiy_i_graham_hull/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <vector>
7
8 #include "makovskiy_i_graham_hull/common/include/common.hpp"
9
10 namespace makovskiy_i_graham_hull {
11
12 namespace {
13
14 double CrossProduct(const Point &o, const Point &a, const Point &b) {
15
2/2
✓ Branch 0 taken 10648 times.
✓ Branch 1 taken 15872 times.
 26520 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
16 }
17
18 double DistSq(const Point &a, const Point &b) {
19 36688 return ((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y));
20 }
21
22 56 size_t FindMinPointIndex(const std::vector<Point> &points) {
23 size_t min_idx = 0;
24
2/2
✓ Branch 0 taken 26576 times.
✓ Branch 1 taken 56 times.
 26632 for (size_t i = 1; i < points.size(); ++i) {
25
3/4
✓ Branch 0 taken 26576 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 504 times.
✓ Branch 3 taken 26072 times.
 26576 if (points[i].y < points[min_idx].y - 1e-9 ||
26
3/4
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 26072 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 504 times.
 26576 (std::abs(points[i].y - points[min_idx].y) <= 1e-9 && points[i].x < points[min_idx].x)) {
27 min_idx = i;
28 }
29 }
30 56 return min_idx;
31 }
32
33 56 std::vector<Point> FilterPoints(const std::vector<Point> &points, const Point &p0) {
34
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 std::vector<Point> filtered;
35 filtered.push_back(points[0]);
36
2/2
✓ Branch 0 taken 15928 times.
✓ Branch 1 taken 56 times.
 15984 for (size_t i = 1; i < points.size(); ++i) {
37
4/4
✓ Branch 0 taken 26520 times.
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 10648 times.
✓ Branch 3 taken 15872 times.
 26576 while (i < points.size() - 1 && std::abs(CrossProduct(p0, points[i], points[i + 1])) < 1e-9) {
38 i++;
39 }
40 filtered.push_back(points[i]);
41 }
42 56 return filtered;
43 }
44
45 40 std::vector<Point> BuildHull(const std::vector<Point> &filtered) {
46
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<Point> hull;
47 hull.push_back(filtered[0]);
48 hull.push_back(filtered[1]);
49 hull.push_back(filtered[2]);
50
51
2/2
✓ Branch 0 taken 15832 times.
✓ Branch 1 taken 40 times.
 15872 for (size_t i = 3; i < filtered.size(); ++i) {
52
3/4
✓ Branch 0 taken 31632 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 15800 times.
✓ Branch 3 taken 15832 times.
 31632 while (hull.size() > 1 && CrossProduct(hull[hull.size() - 2], hull.back(), filtered[i]) <= 1e-9) {
53 hull.pop_back();
54 }
55 hull.push_back(filtered[i]);
56 }
57 40 return hull;
58 }
59
60 } // namespace
61
62
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 ConvexHullGrahamSEQ::ConvexHullGrahamSEQ(const InType &in) {
63 SetTypeOfTask(GetStaticTypeOfTask());
64
1/2
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
 72 GetInput() = in;
65 72 }
66
67 72 bool ConvexHullGrahamSEQ::ValidationImpl() {
68 72 return true;
69 }
70
71 72 bool ConvexHullGrahamSEQ::PreProcessingImpl() {
72 72 return true;
73 }
74
75 72 bool ConvexHullGrahamSEQ::RunImpl() {
76 72 InType points = GetInput();
77
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 56 times.
 72 if (points.size() < 3) {
78
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = points;
79 return true;
80 }
81
82 56 size_t min_idx = FindMinPointIndex(points);
83
84 std::swap(points[0], points[min_idx]);
85 56 Point p0 = points[0];
86
87 377160 std::sort(points.begin() + 1, points.end(), [&p0](const Point &a, const Point &b) {
88
2/2
✓ Branch 0 taken 36688 times.
✓ Branch 1 taken 340416 times.
 377104 double cp = CrossProduct(p0, a, b);
89
2/2
✓ Branch 0 taken 36688 times.
✓ Branch 1 taken 340416 times.
 377104 if (std::abs(cp) < 1e-9) {
90 36688 return DistSq(p0, a) < DistSq(p0, b);
91 }
92 340416 return cp > 0;
93 });
94
95
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 InType filtered = FilterPoints(points, p0);
96
97
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 40 times.
 56 if (filtered.size() < 3) {
98
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 GetOutput() = filtered;
99 return true;
100 }
101
102
1/4
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 40 GetOutput() = BuildHull(filtered);
103 40 return true;
104 }
105
106 72 bool ConvexHullGrahamSEQ::PostProcessingImpl() {
107 72 return true;
108 }
109
110 } // namespace makovskiy_i_graham_hull
111