// A refinement of an order n^3 brute-force algorithm to find the size of the
// largest subset of collinear points in a point set.  The algorithm finds the
// slope between a point and every other point in the set and then groups
// points by slope.  Repeating this for every point in the set takes could take
// O(n^3) work, but the average case should be order n^2 log n.
//
// CS 306 - Computer Algorithms II
// Fall '08

#include <algorithm>
#include "mcp-sorted.h"


typedef std::vector<slope> slope_list
typedef slope_list::iterator slopes_iter
typedef slope_list::const_iterator slopes_citer


// Deja vu c++ style;

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


namespace mcp_sorted {

  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 slope_list
get_slopes(const point & pt, points_citer b, const points_citer & e) {

  // Return a list of all slopes beteen the given point and all points in the
  // range [b, e).

  slope_list slopes

  while (b ≠ e)
    slopes.push_back(get_slope(pt, *b++))

  return slopes
  }


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

  // Return the size of a largest subset of points in [b..e) that lie on a
  // line passing through the given point.

  slope_list slopes = get_slopes(pt, b, e)

  std::sort(slopes.begin(), slopes.end())

  return max_slope_group_size(slopes)
  }


static unsigned
max_slope_group_size(const slope_list & slopes) {

  // Return the size of the largest group of contiguous identical slopes in the
  // given slope list.

  const unsigned n = slopes.size()
  unsigned mx = 0
  unsigned begin = 0

  for (unsigned i = 1; i < n; i++)
    if (slopes[i] ≠ slopes[begin]) {
      mx = std::max(mx, i - begin)
      begin = i
      }
  mx = std::max(mx, n - begin)

  return mx
  }


// $Log:$