// A simple O(n^3) brute-force algorithm to find the size of the largest set of
// collinear points in a point set.
//
// CS 306 - Computer Algorithms II
// Fall '08

#include "mcp-looped.h"


// Deja vu c++ style;

   static unsigned 
     max_col_pts(const point &, points_citer, const points_citer &)


namespace mcp_looped {

  void init() {
    }


  unsigned 
  answer(const point_set & points) {

    unsigned mx = 0
    const points_citer e = points.end()

    for (points_citer i = points.begin(); i ≠ e; i++)
      mx = std::max(mx, max_col_pts(*i, i + 1, e))

    return mx
    }
  }


static unsigned 
max_col_pts(const point & pt1, const point & pt2, 
	    points_citer b, const points_citer & e) {

  // Return the size of the largest set of points in [b..e) that are collinear
  // with the line segment (pt1, pt2).

  unsigned mx = 2
  const slope s = get_slope(pt1, pt2)

  while (b ≠ e)
    if (s == get_slope(pt1, *b++))
      mx++

  return mx
  }


static unsigned 
max_col_pts(const point & pt, points_citer b, const points_citer & e) {

  // Return the size of the largest set of points in [b..e) that are collinear
  // with the given pt.

  unsigned mx = 0
  
  while (b ≠ e) {
    const point & pt2 = *b++
    mx = std::max(mx, max_col_pts(pt, pt2, b, e))
    }

  return mx
  }


// $Log:$