## Algoritmo de ConvexHull.

Cualquier duda no dudes en contactar.

/**
* Author: Johan Sannemo
* Date: 2017-04-16
* Source: Basic algorithm knowledge
* Description:
\\\begin{minipage}{75mm}
Returns a vector of indices of the convex hull in counter-clockwise order.
Points on the edge of the hull between two other points are not considered part of the hull.
\end{minipage}
\begin{minipage}{15mm}
\vspace{-6mm}
\includegraphics[width=\textwidth]{../content/geometry/ConvexHull}
\vspace{-6mm}
\end{minipage}
* Status: tested with Kattis problems convexhull
* Usage:
* 	vector<P> ps, hull;
*  trav(i, convexHull(ps)) hull.push_back(ps[i]);
* Time: O(n \log n)
*/
#pragma once

#include "Point.h"

typedef Point<ll> P;
pair<vi, vi> ulHull(const vector<P>& S) {
vi Q(sz(S)), U, L;
iota(all(Q), 0);
sort(all(Q), [&S](int a, int b){ return S[a] < S[b]; });
trav(it, Q) {
#define ADDP(C, cmp) while (sz(C) > 1 && S[C[sz(C)-2]].cross(\
S[it], S[C.back()]) cmp 0) C.pop_back(); C.push_back(it);
}
return {U, L};
}

vi convexHull(const vector<P>& S) {
vi u, l; tie(u, l) = ulHull(S);
if (sz(S) <= 1) return u;
if (S[u[0]] == S[u[1]]) return {0};
l.insert(l.end(), u.rbegin()+1, u.rend()-1);
return l;
}