GCC Code Coverage Report

Directory: ./
File: tasks/dergachev_a_graham_scan/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 44 48 91.7%
Functions: 8 8 100.0%
Branches: 35 66 53.0%
Line Branch Exec Source
1 #include "dergachev_a_graham_scan/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <utility>
6 #include <vector>
7
8 #include "dergachev_a_graham_scan/common/include/common.hpp"
9
10 namespace dergachev_a_graham_scan {
11
12 namespace {
13
14 double CrossProduct(const Point &o, const Point &a, const Point &b) {
15 155184 return ((a.x - o.x) * (b.y - o.y)) - ((a.y - o.y) * (b.x - o.x));
16 }
17
18 double DistSquared(const Point &a, const Point &b) {
19 ✗ double dx = a.x - b.x;
20 ✗ double dy = a.y - b.y;
21 ✗ return (dx * dx) + (dy * dy);
22 }
23
24 const double kPi = std::acos(-1.0);
25
26 88 int FindPivotIndex(const std::vector<Point> &pts) {
27 int pivot_idx = 0;
28 9688 for (int i = 1; std::cmp_less(i, pts.size()); i++) {
29
5/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 7160 times.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 7168 times.
✓ Branch 5 taken 2432 times.
 9600 if (pts[i].y < pts[pivot_idx].y || (pts[i].y == pts[pivot_idx].y && pts[i].x < pts[pivot_idx].x)) {
30 pivot_idx = i;
31 }
32 }
33 88 return pivot_idx;
34 }
35
36 88 void SortByAngle(std::vector<Point> &pts) {
37 88 Point pivot = pts[0];
38 145688 std::sort(pts.begin() + 1, pts.end(), [&pivot](const Point &a, const Point &b) {
39 145600 double cross = CrossProduct(pivot, a, b);
40
2/2
✓ Branch 0 taken 37720 times.
✓ Branch 1 taken 107880 times.
 145600 if (cross > 0.0) {
41 return true;
42 }
43
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 37720 times.
 37720 if (cross < 0.0) {
44 return false;
45 }
46 ✗ return DistSquared(pivot, a) < DistSquared(pivot, b);
47 });
48 88 }
49
50 } // namespace
51
52 104 DergachevAGrahamScanSEQ::DergachevAGrahamScanSEQ(const InType &in) {
53 SetTypeOfTask(GetStaticTypeOfTask());
54 104 GetInput() = in;
55 GetOutput() = 0;
56 104 }
57
58 104 bool DergachevAGrahamScanSEQ::ValidationImpl() {
59 104 return GetInput() >= 0;
60 }
61
62
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
 104 bool DergachevAGrahamScanSEQ::PreProcessingImpl() {
63 hull_.clear();
64 104 int n = GetInput();
65
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 96 times.
 104 if (n <= 0) {
66 points_.clear();
67 8 return true;
68 }
69 96 points_.resize(n);
70 96 double step = (2.0 * kPi) / n;
71
2/2
✓ Branch 0 taken 9624 times.
✓ Branch 1 taken 96 times.
 9720 for (int i = 0; i < n; i++) {
72 9624 points_[i] = {.x = std::cos(step * i), .y = std::sin(step * i)};
73 }
74
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 24 times.
 96 if (n > 3) {
75 72 points_.push_back({.x = 0.0, .y = 0.0});
76 }
77 return true;
78 }
79
80
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
 104 bool DergachevAGrahamScanSEQ::RunImpl() {
81 hull_.clear();
82
2/2
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 16 times.
 104 std::vector<Point> pts(points_.begin(), points_.end());
83 104 int n = static_cast<int>(pts.size());
84
85
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 16 times.
 104 if (n <= 1 ||
86
4/30
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
✗ 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 not taken.
✓ Branch 21 taken 8 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✓ Branch 25 taken 8 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✓ Branch 29 taken 88 times.
 176 std::all_of(pts.begin() + 1, pts.end(), [&](const Point &pt) { return pt.x == pts[0].x && pt.y == pts[0].y; })) {
87
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
 16 if (!pts.empty()) {
88
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 hull_.push_back(pts[0]);
89 }
90 16 return true;
91 }
92
93 88 int pivot_idx = FindPivotIndex(pts);
94 88 std::swap(pts[0], pts[pivot_idx]);
95 88 SortByAngle(pts);
96
97
2/2
✓ Branch 0 taken 9688 times.
✓ Branch 1 taken 88 times.
 9776 for (const auto &p : pts) {
98
4/4
✓ Branch 0 taken 9584 times.
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 9512 times.
✓ Branch 3 taken 72 times.
 9760 while (hull_.size() > 1 && CrossProduct(hull_[hull_.size() - 2], hull_.back(), p) <= 0.0) {
99 hull_.pop_back();
100 }
101
2/2
✓ Branch 0 taken 9240 times.
✓ Branch 1 taken 448 times.
 9688 hull_.push_back(p);
102 }
103
104 return true;
105 }
106
107 104 bool DergachevAGrahamScanSEQ::PostProcessingImpl() {
108 104 GetOutput() = static_cast<int>(hull_.size());
109 104 return true;
110 }
111
112 } // namespace dergachev_a_graham_scan
113