GCC Code Coverage Report

Directory: ./
File: tasks/dergachev_a_graham_scan/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 62 66 93.9%
Functions: 11 11 100.0%
Branches: 66 86 76.7%
Line Branch Exec Source
1 #include "dergachev_a_graham_scan/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <thread>
8 #include <utility>
9 #include <vector>
10
11 #include "dergachev_a_graham_scan/common/include/common.hpp"
12 #include "util/include/util.hpp"
13
14 namespace dergachev_a_graham_scan {
15
16 namespace {
17
18 using Pt = std::pair<double, double>;
19
20 double Cross(const Pt &o, const Pt &a, const Pt &b) {
21 69384 return ((a.first - o.first) * (b.second - o.second)) - ((a.second - o.second) * (b.first - o.first));
22 }
23
24 double Dist2(const Pt &a, const Pt &b) {
25 ✗ double dx = a.first - b.first;
26 ✗ double dy = a.second - b.second;
27 ✗ return (dx * dx) + (dy * dy);
28 }
29
30 const double kPi = std::acos(-1.0);
31
32 46 int FindPivot(const std::vector<Pt> &pts) {
33 int best = 0;
34 4798 for (int i = 1; std::cmp_less(i, pts.size()); i++) {
35
5/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4140 times.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4144 times.
✓ Branch 5 taken 608 times.
 4752 if (pts[i].second < pts[best].second || (pts[i].second == pts[best].second && pts[i].first < pts[best].first)) {
36 best = i;
37 }
38 }
39 46 return best;
40 }
41
42 64660 bool AngleCompare(const Pt &pivot, const Pt &a, const Pt &b) {
43 double c = Cross(pivot, a, b);
44
1/2
✓ Branch 0 taken 64660 times.
✗ Branch 1 not taken.
 64660 if (c != 0.0) {
45 64660 return c > 0.0;
46 }
47 ✗ return Dist2(pivot, a) < Dist2(pivot, b);
48 }
49
50 46 void AngleSort(std::vector<Pt> &pts) {
51 Pt pivot = pts[0];
52
22/24
✓ Branch 0 taken 1058 times.
✓ Branch 1 taken 1508 times.
✓ Branch 2 taken 4750 times.
✓ Branch 3 taken 3362 times.
✓ Branch 4 taken 3520 times.
✓ Branch 5 taken 4634 times.
✓ Branch 6 taken 20858 times.
✓ Branch 7 taken 2816 times.
✓ Branch 8 taken 17998 times.
✓ Branch 9 taken 2816 times.
✓ Branch 10 taken 282 times.
✓ Branch 11 taken 100 times.
✓ Branch 12 taken 158 times.
✓ Branch 13 taken 124 times.
✓ Branch 14 taken 42 times.
✓ Branch 15 taken 82 times.
✓ Branch 16 taken 48 times.
✓ Branch 17 taken 52 times.
✓ Branch 18 taken 44 times.
✓ Branch 19 taken 8 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 72 times.
✓ Branch 23 taken 328 times.
 64102 std::sort(pts.begin() + 1, pts.end(), [&pivot](const Pt &a, const Pt &b) { return AngleCompare(pivot, a, b); });
53 46 }
54
55
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 46 times.
 46 std::vector<Pt> BuildHull(std::vector<Pt> pts) {
56
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 46 times.
 46 if (pts.size() < 2) {
57 return pts;
58 }
59 46 int pivot = FindPivot(pts);
60 46 std::swap(pts[0], pts[pivot]);
61 46 AngleSort(pts);
62 46 std::vector<Pt> hull;
63
2/2
✓ Branch 0 taken 4798 times.
✓ Branch 1 taken 46 times.
 4844 for (const auto &p : pts) {
64
4/4
✓ Branch 0 taken 4724 times.
✓ Branch 1 taken 92 times.
✓ Branch 2 taken 18 times.
✓ Branch 3 taken 4706 times.
 4816 while (hull.size() > 1 && Cross(hull[hull.size() - 2], hull.back(), p) <= 0.0) {
65 hull.pop_back();
66 }
67 hull.push_back(p);
68 }
69 return hull;
70 }
71
72 int ChunkLen(int idx, int total, int parts) {
73
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 return (total / parts) + ((idx < (total % parts)) ? 1 : 0);
74 }
75
76 22 std::vector<Pt> ThreadedHull(const std::vector<Pt> &pts) {
77 22 int n = static_cast<int>(pts.size());
78 22 int num_threads = ppc::util::GetNumThreads();
79
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 12 times.
 22 if (n < num_threads * 4) {
80
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 20 return BuildHull({pts.begin(), pts.end()});
81 }
82 12 std::vector<std::vector<Pt>> partial(num_threads);
83 12 std::vector<std::thread> workers;
84 int off = 0;
85
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int ti = 0; ti < num_threads; ti++) {
86 int len = ChunkLen(ti, n, num_threads);
87 24 workers.emplace_back(
88
2/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 24 times.
✗ Branch 6 not taken.
 72 [&partial, &pts, off, len, ti]() { partial[ti] = BuildHull({pts.begin() + off, pts.begin() + off + len}); });
89 24 off += len;
90 }
91
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (auto &w : workers) {
92
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 w.join();
93 }
94 12 std::vector<Pt> merged;
95
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (const auto &h : partial) {
96 24 merged.insert(merged.end(), h.begin(), h.end());
97 }
98
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 return BuildHull(std::move(merged));
99 12 }
100
101 } // namespace
102
103 26 DergachevAGrahamScanALL::DergachevAGrahamScanALL(const InType &in) {
104 SetTypeOfTask(GetStaticTypeOfTask());
105 26 GetInput() = in;
106 GetOutput() = 0;
107 26 }
108
109 26 bool DergachevAGrahamScanALL::ValidationImpl() {
110 26 return GetInput() >= 0;
111 }
112
113
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
 26 bool DergachevAGrahamScanALL::PreProcessingImpl() {
114 hull_.clear();
115 26 int n = GetInput();
116
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 24 times.
 26 if (n <= 0) {
117 points_.clear();
118 2 return true;
119 }
120 24 points_.resize(n);
121 24 double step = (2.0 * kPi) / n;
122
2/2
✓ Branch 0 taken 2406 times.
✓ Branch 1 taken 24 times.
 2430 for (int i = 0; i < n; i++) {
123 2406 points_[i] = {std::cos(step * i), std::sin(step * i)};
124 }
125
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 if (n > 3) {
126 18 points_.emplace_back(0.0, 0.0);
127 }
128 return true;
129 }
130
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26 times.
 26 bool DergachevAGrahamScanALL::RunImpl() {
132 hull_.clear();
133
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 22 times.
 26 std::vector<Pt> pts(points_.begin(), points_.end());
134
135
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 22 times.
 26 if (pts.size() <= 1) {
136
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 hull_ = pts;
137 return true;
138 }
139
140
1/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 22 hull_ = ThreadedHull(pts);
141
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 MPI_Barrier(MPI_COMM_WORLD);
142 return true;
143 }
144
145 26 bool DergachevAGrahamScanALL::PostProcessingImpl() {
146 26 GetOutput() = static_cast<int>(hull_.size());
147 26 return true;
148 }
149
150 } // namespace dergachev_a_graham_scan
151