Attempt to solve the problem described here: http://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/lines.html

collinear.cpp

#define BOOST_TEST_MODULE collinear
#include <boost/test/unit_test.hpp>
#include <boost/range/algorithm/generate.hpp>
#include <set>
#include <cmath>

struct Point {
  int x;
  int y;
};
inline bool operator== (const Point& a, const Point& b) {
  return std::tie(a.x, a.y) == std::tie(b.x, b.y);
}
inline bool operator!= (const Point& a, const Point& b) {
  return !operator==(a, b);
}
inline bool operator< (const Point& a, const Point& b) {
  return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}
inline std::ostream& operator<<(std::ostream& os, const Point& p) {
  return os << '[' << p.x << ',' << p.y << ']';
}

struct Segment {
  Point start;
  Point end;

  Segment(const Point& s, const Point& e) : start(s), end(e) {}
  auto slope() const {
    return double(end.y - start.y) / double(end.x - start.x);
  }
};
inline bool operator== (const Segment& a, const Segment& b) {
  return std::tie(a.start, a.end) == std::tie(b.start, b.end);
}
inline bool operator< (const Segment& a, const Segment& b) {
  return std::tie(a.start, a.end) < std::tie(b.start, b.end);
}
inline std::ostream& operator<<(std::ostream& os, const Segment& s) {
  return os << s.start << " -> " << s.end;
}

template <typename InRange, typename OutIt>
void find_collinear(InRange&& in, OutIt out)
{
  // Sort the points
  std::sort(std::begin(in), std::end(in));

  // Construct segments
  std::vector<Segment> segs;
  for (auto it = std::begin(in); it != std::end(in); ++it) {
    for (auto eit = std::next(it); eit != std::end(in); ++eit) {
      segs.emplace_back(*it, *eit);
    }
  }

  // Sort the segments into slope order, then on endpoint
  std::sort(std::begin(segs), std::end(segs), [] (const Segment& a, const Segment& b) {
      const auto a_slope = a.slope();
      const auto b_slope = b.slope();
      return std::tie(a_slope, a.end) < std::tie(b_slope, b.end);
    });

  if (segs.size() < 5)
    return;

  // Write out 4+ consecutive segments with same slope/end
  auto sit = std::begin(segs);
  auto mpt = std::begin(segs)->start;
  for (auto it = std::next(sit); it != std::end(segs); ++it) {
    // continuing subrange?
    if (it->slope() == sit->slope() && it->end == sit->end) {
      mpt = std::min(mpt, it->start);
      continue;
    }
    // we now have a range [sit, it). Write it out if we have enough elements
    // (we need at least 5 collinear points, hence we need at least 4
    // segments)
    if (std::distance(sit, it) >= 4) {
      *out++ = Segment{mpt, sit->end};
    }
    // Start collecting a new range
    sit = it;
    mpt = it->start;
  }

  if (std::distance(sit, std::end(segs)) >= 4) {
    *out++ = Segment{mpt, sit->end};
  }
}

BOOST_AUTO_TEST_CASE(_5x5Grid)
{
  static constexpr unsigned N = 5;

  std::vector<Point> in{N * N};
  boost::generate(in, [i=0] () mutable {
      const auto d = std::div(i++, N);
      return Point{d.quot, d.rem};
    });

  // Use unordered container to detect possible dupes
  std::vector<Segment> out;
  find_collinear(in, std::inserter(out, out.begin()));
  std::sort(std::begin(out), std::end(out));

  // expected outputs are going to be the 5 horizontal, 5 vertical, and 2 diagonals.
  const std::set<Segment> exp = {
    // horizontal
    {{0, 0}, {0, 4}},
    {{1, 0}, {1, 4}},
    {{2, 0}, {2, 4}},
    {{3, 0}, {3, 4}},
    {{4, 0}, {4, 4}},
    // vertical
    {{0, 0}, {4, 0}},
    {{0, 1}, {4, 1}},
    {{0, 2}, {4, 2}},
    {{0, 3}, {4, 3}},
    {{0, 4}, {4, 4}},
    // diagonals
    {{0, 0}, {4, 4}},
    {{0, 4}, {4, 0}}
  };
  BOOST_TEST(out == exp, boost::test_tools::per_element());
}