GCC Code Coverage Report

Directory: ./
File: tasks/dergachev_a_graham_scan/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 42 46 91.3%
Functions: 8 8 100.0%
Branches: 30 60 50.0%
Line Branch Exec Source
1 #include "dergachev_a_graham_scan/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <utility>
8 #include <vector>
9
10 #include "dergachev_a_graham_scan/common/include/common.hpp"
11
12 namespace dergachev_a_graham_scan {
13
14 namespace {
15
16 using Pt = std::pair<double, double>;
17
18 double CrossProduct(const Pt &o, const Pt &a, const Pt &b) {
19 77592 return ((a.first - o.first) * (b.second - o.second)) - ((a.second - o.second) * (b.first - o.first));
20 }
21
22 double DistSquared(const Pt &a, const Pt &b) {
23 ✗ double dx = a.first - b.first;
24 ✗ double dy = a.second - b.second;
25 ✗ return (dx * dx) + (dy * dy);
26 }
27
28 const double kPi = std::acos(-1.0);
29
30 bool IsLowerLeft(const Pt &a, const Pt &b) {
31 return a.second < b.second || (a.second == b.second && a.first < b.first);
32 }
33
34 44 int FindPivotIndex(const std::vector<Pt> &pts) {
35 44 int size = static_cast<int>(pts.size());
36 int pivot_idx = 0;
37 44 #pragma omp parallel default(none) shared(pts, size, pivot_idx)
38 {
39 int local_idx = 0;
40 #pragma omp for nowait
41 for (int i = 1; i < size; i++) {
42 if (IsLowerLeft(pts[i], pts[local_idx])) {
43 local_idx = i;
44 }
45 }
46 #pragma omp critical
47 {
48 if (IsLowerLeft(pts[local_idx], pts[pivot_idx])) {
49 pivot_idx = local_idx;
50 }
51 }
52 }
53 44 return pivot_idx;
54 }
55
56 44 void SortByAngle(std::vector<Pt> &pts) {
57 Pt pivot = pts[0];
58 72844 std::sort(pts.begin() + 1, pts.end(), [&pivot](const Pt &a, const Pt &b) {
59 72800 double cross = CrossProduct(pivot, a, b);
60
2/2
✓ Branch 0 taken 18860 times.
✓ Branch 1 taken 53940 times.
 72800 if (cross > 0.0) {
61 return true;
62 }
63
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18860 times.
 18860 if (cross < 0.0) {
64 return false;
65 }
66 ✗ return DistSquared(pivot, a) < DistSquared(pivot, b);
67 });
68 44 }
69
70 } // namespace
71
72 52 DergachevAGrahamScanOMP::DergachevAGrahamScanOMP(const InType &in) {
73 SetTypeOfTask(GetStaticTypeOfTask());
74 52 GetInput() = in;
75 GetOutput() = 0;
76 52 }
77
78 52 bool DergachevAGrahamScanOMP::ValidationImpl() {
79 52 return GetInput() >= 0;
80 }
81
82
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 52 bool DergachevAGrahamScanOMP::PreProcessingImpl() {
83 hull_.clear();
84 52 int n = GetInput();
85
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 48 times.
 52 if (n <= 0) {
86 points_.clear();
87 4 return true;
88 }
89 48 points_.resize(n);
90
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 12 times.
 48 double step = (2.0 * kPi) / n;
91 auto *pts_data = points_.data();
92 48 #pragma omp parallel for default(none) shared(pts_data, step, n)
93 for (int i = 0; i < n; i++) {
94 pts_data[i] = {std::cos(step * i), std::sin(step * i)};
95 }
96
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 12 times.
 48 if (n > 3) {
97 36 points_.emplace_back(0.0, 0.0);
98 }
99 return true;
100 }
101
102
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 52 bool DergachevAGrahamScanOMP::RunImpl() {
103 hull_.clear();
104
2/2
✓ Branch 1 taken 44 times.
✓ Branch 2 taken 8 times.
 52 std::vector<Pt> pts(points_.begin(), points_.end());
105 52 int n = static_cast<int>(pts.size());
106
107
3/4
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
 52 if (n <= 1 || std::all_of(pts.begin() + 1, pts.end(),
108
3/28
✗ Branch 0 not taken.
✓ Branch 1 taken 36 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 4 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✓ Branch 25 taken 4 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 44 [&](const Pt &pt) { return pt.first == pts[0].first && pt.second == pts[0].second; })) {
109
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (!pts.empty()) {
110
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 hull_.push_back(pts[0]);
111 }
112 8 return true;
113 }
114
115 44 int pivot_idx = FindPivotIndex(pts);
116 44 std::swap(pts[0], pts[pivot_idx]);
117 44 SortByAngle(pts);
118
119
2/2
✓ Branch 0 taken 4844 times.
✓ Branch 1 taken 44 times.
 4888 for (const auto &p : pts) {
120
4/4
✓ Branch 0 taken 4792 times.
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 4756 times.
✓ Branch 3 taken 36 times.
 4880 while (hull_.size() > 1 && CrossProduct(hull_[hull_.size() - 2], hull_.back(), p) <= 0.0) {
121 hull_.pop_back();
122 }
123
2/2
✓ Branch 0 taken 4620 times.
✓ Branch 1 taken 224 times.
 4844 hull_.push_back(p);
124 }
125
126 return true;
127 }
128
129 52 bool DergachevAGrahamScanOMP::PostProcessingImpl() {
130 52 GetOutput() = static_cast<int>(hull_.size());
131 52 return true;
132 }
133
134 } // namespace dergachev_a_graham_scan
135