#Modified code #include #include #include #include #include #include

namespace {
 class Vector2D
 {
 int x;
 int y;
 // For sorting - lowest y first, then lowest x
 auto tie() const { return std::tie(y, x); }
 public:
 Vector2D(int x, int y) : x(x), y(y) {}
 Vector2D operator-(const Vector2D& other) const
 {
 return {x - other.x, y - other.y};
 }
 bool operator<(const Vector2D& other) const
 {
 return tie() < other.tie();
 }
 bool operator==(const Vector2D& other) const
 {
 return tie() == other.tie();
 }
 bool is_clockwise_to(const Vector2D& other) const
 {
 // a positive determinant indicates clockwise, and negative anticlockwise
 // zero means collinear (which we consider "not clockwise")
 return y * other.x - x * other.y > 0;
 }
 friend std::ostream& operator<<(std::ostream& os, const Vector2D& v)
 {
 return os << v.x << ' ' << v.y << '\n';
 }
 };
 using namespace std::rel_ops;
}
// find next convex hull vertex
Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
 for (auto const& target: coords)
 {
 auto const vecTarget = target - source;
 if (vecTarget != Vector2D{ 0, 0 } &&
 std::all_of(coords.begin(), coords.end(),
 [&](const auto& c) {
 return c == target
 || c == source
 || (c - source).is_clockwise_to(vecTarget);}))
 {
 return target;
 }
 }
 // degenerate case
 return source;
}
std::vector<Vector2D> readInputPoints()
{
 std::ifstream file;
 file.open("data.txt");
 if (!file.is_open()) {
 std::cerr << "unable to open file" << std::endl;
 return {};
 }
 std::vector<Vector2D> coords;
 // total number of points
 std::size_t nPoints = 0;
 file >> nPoints;
 if (!file) return {};
 coords.reserve(nPoints);
 while (--nPoints) {
 int x, y;
 file >> x >> y;
 if (!file) return {};
 coords.emplace_back(x, y);
 }
 return coords;
}
int main()
{
 const std::vector<Vector2D> coords = readInputPoints();
 if (coords.empty()) {
 std::cerr << "Could not read inputs!" << std::endl;
 return 1;
 }
 // find the topmost
 auto const& topMost = *std::max_element(coords.begin(), coords.end());
 auto current = topMost;
 do {
 current = nextVertex(coords, current);
 std::cout << current;
 } while (current != topMost);
}

Modified code

#include <fstream>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include <algorithm>
namespace {
 class Vector2D
 {
 int x;
 int y;
 // For sorting - lowest y first, then lowest x
 auto tie() const { return std::tie(y, x); }
 public:
 Vector2D(int x, int y) : x(x), y(y) {}
 Vector2D operator-(const Vector2D& other) const
 {
 return {x - other.x, y - other.y};
 }
 bool operator<(const Vector2D& other) const
 {
 return tie() < other.tie();
 }
 bool operator==(const Vector2D& other) const
 {
 return tie() == other.tie();
 }
 bool is_clockwise_to(const Vector2D& other) const
 {
 // a positive determinant indicates clockwise, and negative anticlockwise
 // zero means collinear (which we consider "not clockwise")
 return y * other.x - x * other.y > 0;
 }
 friend std::ostream& operator<<(std::ostream& os, const Vector2D& v)
 {
 return os << v.x << ' ' << v.y << '\n';
 }
 };
 using namespace std::rel_ops;
}
// find next convex hull vertex
Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
 for (auto const& target: coords)
 {
 auto const vecTarget = target - source;
 if (vecTarget != Vector2D{ 0, 0 } &&
 std::all_of(coords.begin(), coords.end(),
 [&](const auto& c) {
 return c == target
 || c == source
 || (c - source).is_clockwise_to(vecTarget);}))
 {
 return target;
 }
 }
 // degenerate case
 return source;
}
std::vector<Vector2D> readInputPoints()
{
 std::ifstream file;
 file.open("data.txt");
 if (!file.is_open()) {
 std::cerr << "unable to open file" << std::endl;
 return {};
 }
 std::vector<Vector2D> coords;
 // total number of points
 std::size_t nPoints = 0;
 file >> nPoints;
 if (!file) return {};
 coords.reserve(nPoints);
 while (--nPoints) {
 int x, y;
 file >> x >> y;
 if (!file) return {};
 coords.emplace_back(x, y);
 }
 return coords;
}
int main()
{
 const std::vector<Vector2D> coords = readInputPoints();
 if (coords.empty()) {
 std::cerr << "Could not read inputs!" << std::endl;
 return 1;
 }
 // find the topmost
 auto const& topMost = *std::max_element(coords.begin(), coords.end());
 auto current = topMost;
 do {
 current = nextVertex(coords, current);
 std::cout << current;
 } while (current != topMost);
}

Notice that this came out simpler than my first improved version above, and much simpler than the original.

Notice that this came out simpler than my first improved version above, and much simpler than the original. (The lambda that captures a reference to source might be more advanced than you're used to, though).

Improve the algorithm

The current algorithm looks at the next two points from each vertex, so it scales as O(hn2) where n is the number of points and h the number of bounding points.

We can use the knowledge that all points lie on the same side of some line through any bounding point to only test each candidate once - if it's further to the left (or right, depending which way round the hull we want to go) of the previous best candidate, then it's a better choice. This, of course, is simply choosing the maximum of a new criterion, and it makes our code scale as O(hn).

Here's what I mean:

Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
 // order by direction from source - this works because we know that all
 // points lie on the same side of a line through source.
 auto const by_angle = [&source](const Vector2D& a, const Vector2D& b) {
 return (a - source).is_clockwise_to(b - source);
 };
 return *max_element(coords.begin(), coords.end(), by_angle);
}

Notice that this came out simpler than my first improved version above, and much simpler than the original.

You might want to make a refinement so that collinear points sort in order of distance from point (use std::hypot() in the <cmath> header to add a member to Vector2D). Without that, we could have source be directly between two other bounding points, and they would compare equal.

Consider adding some test cases with collinear bounding points and some with trivial point sets (1 or 2 points), as these will probably require minor modifications.