Envolvente convexa

#include <bits/stdc++.h>
 
using namespace std;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORE(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define trav(a, x) for (auto &a : x)
 
#define f first
#define s second
#define bk back()
#define pb push_back
 
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
 
int N, Q;
 
const int MX = 2e5 + 5;
 
using T = long long;  // or long long
const T EPS = 1e-9;   // might want to change
using P = pair<T, T>;
using vP = vector<P>;
using Line = pair<P, P>;
 
T sq(T a) { return a * a; }                       // square
T norm(const P &p) { return sq(p.f) + sq(p.s); }  // x^2 + y^2
 
// basic operations
P operator-(const P &l, const P &r) { return P(l.f - r.f, l.s - r.s); }
 
T cross(const P &a, const P &b) { return a.f * b.s - a.s * b.f; }  // cross product
T cross(const P &p, const P &a, const P &b) {                      // cross product
	return cross(a - p, b - p);
}
 
using vi = vector<int>;
using vP = vector<P>;
 
vi hullInd(const vP &v) {
	int ind = int(min_element(all(v)) - begin(v));
	vi cand, hull{ind};
	F0R(i, sz(v)) if (v[i] != v[ind]) cand.pb(i);
 
	sort(all(cand), [&](int a, int b) {  // sort by angle, tiebreak by distance
		P x = v[a] - v[ind], y = v[b] - v[ind];
		T t = cross(x, y);
		return t != 0 ? t > 0 : norm(x) < norm(y);
	});
 
	trav(c, cand) {  // for every point
		while (sz(hull) > 1 && cross(v[end(hull)[-2]], v[hull.bk], v[c]) <= 0) {
			hull.pop_back();  // pop until counterclockwise and size > 1
		}
		hull.pb(c);
	}
 
	return hull;
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	for (;;) {
		int n;
		cin >> n;
		if (!n) break;
		vP pts(n);
 
		F0R(i, n) {
			long long a, b;
			cin >> a >> b;
			pts[i] = P(a, b);
		}
 
		vi ret = hullInd(pts);  // gets hull indices of convex hull
 
		cout << sz(ret) << '\n';
		trav(a, ret) { cout << pts[a].first << " " << pts[a].second << '\n'; }
	}
}

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int, int>;
 
vector<pii> points;
vector<pii> hull;
 
// producto cruz, el área con signo de estos tres puntos
int area(pii O, pii P, pii Q) {
	return (P.first - O.first) * (Q.second - O.second) -
	       (P.second - O.second) * (Q.first - O.first);
}
 
void monotone_chain() {
	// ordenar respecto de las coordenadas x e y
	sort(points.begin(), points.end());
	// dejar los puntos distintos
	points.erase(unique(points.begin(), points.end()), points.end());
	int n = points.size();
 
	// 1 o 2 puntos siempre están en la envolvente convexa
	if (n < 3) {
		hull = points;
		return;
	}
 
	// envolvente inferior
	for (int i = 0; i < n; i++) {
		// si con el nuevo punto points[i] se forma un giro a la
		// derecha, sacamos el último punto de la envolvente y
		// seguimos testeando
		while (hull.size() > 1 &&
		       area(hull[hull.size() - 2], hull.back(), points[i]) <= 0)
 
			hull.pop_back();
		// si no, agregar el punto a la envolvente
		hull.push_back(points[i]);
	}
 
	// envolvente superior, con la misma lógica que la inferior
	auto lower_hull_length = hull.size();
	for (int i = n - 2; i >= 0; i--) {
		// solo podemos sacar un punto si todavía quedan puntos en la
		// envolvente superior
		while (hull.size() > lower_hull_length &&
		       area(hull[hull.size() - 2], hull.back(), points[i]) <= 0)
			hull.pop_back();
		hull.push_back(points[i]);
	}
	// borrar point[0], que se agregó dos veces
	hull.pop_back();
}
 
int main() {
	cin.tie(0)->sync_with_stdio(false);
 
	int n;
	cin >> n;
	while (n != 0) {
		points.assign(n, {});
		hull = {};
		for (auto &p : points) cin >> p.first >> p.second;
		monotone_chain();
 
		cout << hull.size() << "\n";
		for (auto &p : hull) cout << p.first << " " << p.second << "\n";
 
		cin >> n;
	}
 
	return 0;
}

import java.io.*;
import java.util.*;
 
public class ConvexHull {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(in.readLine());
		while (N > 0) {
			// usar un hashset para dejar los puntos distintos
			Set<V2> input = new HashSet<V2>(N);
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				input.add(new V2(Integer.parseInt(st.nextToken()),
				                 Integer.parseInt(st.nextToken())));
			}
			V2[] points = new V2[input.size()];
			input.toArray(points);
			var hull = monotoneChain(points);
 
			System.out.println(hull.size());
			for (V2 p : hull) { System.out.println(String.format("%d %d", p.X, p.Y)); }
 
			N = Integer.parseInt(in.readLine());
		}
		in.close();
	}
 
	// calcular la envolvente convexa de los puntos dados en orden antihorario
	private static List<V2> monotoneChain(V2[] P) {
		// para un conjunto con menos de 3 puntos, el conjunto de esos
		// puntos ya es la envolvente convexa
		if (P.length < 3) { return Arrays.asList(P); }
 
		List<V2> hull = new ArrayList<V2>();
		// ordenar los puntos por su valor de x en orden creciente. En
		// caso de empate, ordenar por sus valores de y
		Arrays.sort(P);
 
		// envolvente inferior
		for (int i = 0; i < P.length; i++) {
			/*
			 * si el último punto de hull está a la izquierda del
			 * punto actual, es decir forma un giro a la derecha,
			 * entonces podemos sacar el último punto hasta que solo
			 * queden giros a la izquierda
			 */
			while (hull.size() > 1 && sign(hull.get(hull.size() - 2),
			                               hull.get(hull.size() - 1), P[i]) <= 0)
				hull.remove(hull.size() - 1);
			hull.add(P[i]);
		}
 
		// envolvente superior
		int k = hull.size();
		for (int i = P.length - 2; i >= 0; i--) {
			while (hull.size() > k && sign(hull.get(hull.size() - 2),
			                               hull.get(hull.size() - 1), P[i]) <= 0) {
				hull.remove(hull.size() - 1);
			}
			hull.add(P[i]);
		}
		// El primer punto se agregó dos veces, así que lo sacamos
		hull.remove(hull.size() - 1);
 
		return hull;
	}
 
	/*
	 * devuelve -1 si el segmento OP está a la izquierda del segmento OQ;
	 * y 1 en el caso contrario; 0 si O, P y Q son colineales.
	 */
	private static int sign(V2 O, V2 P, V2 Q) {
		int area = area(O, P, Q);
		if (area < 0) return -1;
		else if (area > 0) return 1;
		return 0;
	}
 
	// truco del producto cruz, el área con signo de estos tres puntos
	private static int area(V2 O, V2 P, V2 Q) { return P.minus(O).cross(Q.minus(O)); }
 
	private static class V2 implements Comparable<V2> {
		public int X;
		public int Y;
 
		public V2(int x, int y) {
			X = x;
			Y = y;
		}
 
		public V2 minus(V2 other) { return new V2(X - other.X, Y - other.Y); }
 
		// producto "cruz" (wedge) de un vector 2d. si no se está
		// familiarizado con esto, conviene investigar primero
		public int cross(V2 o) { return X * o.Y - Y * o.X; }
 
		@Override
		public int compareTo(ConvexHull.V2 o) {
			int r = X - o.X;
			if (r == 0) return Y - o.Y;
			return r;
		}
 
		@Override
		public boolean equals(Object obj) {
			if (obj == null || !getClass().equals(obj.getClass())) return false;
			return ((V2)obj).X == this.X && ((V2)obj).Y == this.Y;
		}
 
		@Override
		public int hashCode() {
			int hash = 17;
			hash = hash * 13 + X;
			hash = hash * 13 + Y;
			return hash;
		}
	}
}