// Refer to: https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
template <typename T>
inline bool anti_clockwise_less_than(
    const T lhs_x,
    const T lhs_y,
    const T rhs_x,
    const T rhs_y,
    const T center_x,
    const T center_y
    )
{
  if (lhs_x - center_x >= 0 && rhs_x - center_x < 0) {
    return false;
  }

  if (lhs_x - center_x < 0 && rhs_x - center_x >= 0) {
    return true;
  }

  if (lhs_x - center_x == 0 && rhs_x - center_x == 0) {
    if (lhs_y - center_y >= 0 || rhs_y - center_y >= 0) {
      return lhs_y <= rhs_y;
    }
    return rhs_y <= lhs_y;
  }

  // compute the cross product of vectors: (center -> lhs) x (center -> rhs)
  T det = (lhs_x - center_x) * (rhs_y - center_y) - (rhs_x - center_x) * (lhs_y - center_y);
  if (det < 0) {
    return false;
  }
  if (det > 0) {
    return true;
  }

  // points lhs and rhs are on the same line from the center
  // check which point is closer to the center
  T lhs_d = (lhs_x - center_x) * (lhs_x - center_x) + (lhs_y - center_y) * (lhs_y - center_y);
  T rhs_d = (rhs_x - center_x) * (rhs_x - center_x) + (rhs_y - center_y) * (lhs_y - center_y);
  return lhs_d <= rhs_d;
}

template <typename T>
inline void get_center_point(
    T& center_x,
    T& center_y,
    const int num_pts,
    T* pts
    )
{
  center_x = T(0);
  center_y = T(0);
  for (int i = 0; i < num_pts; ++i) {
    center_x += pts[i*2];
    center_y += pts[i*2+1];
  }
  center_x /= num_pts;
  center_y /= num_pts;
}

template <typename T>
inline void anti_clockwise_sort(const int num_pts, T* pts)
{
  T center_x;
  T center_y;
  get_center_point(center_x, center_y, num_pts, pts);

  for (int i = 0; i < num_pts; ++i) {
    for (int j = 0; j < num_pts; ++j) {
      T lhs_x = pts[i*2];
      T lhs_y = pts[i*2+1];
      T rhs_x = pts[j*2];
      T rhs_y = pts[j*2+1];
      if (anti_clockwise_less_than(lhs_x, lhs_y, rhs_x, rhs_y, center_x, center_y)) {
        pts[i*2] = rhs_x;
        pts[i*2+1] = rhs_y;
        pts[j*2] = lhs_x;
        pts[j*2+1] = lhs_y;
      }
    }
  }
}