Sort Points by Argument

Solución

La idea de este problema es bastante directa. Definamos el “argumento” de un punto como el ángulo que forma con el origen. Dados $n$ puntos $\{P_1,...,P_n\}$ , podemos hallar el argumento del punto $P_i = (x_i,y_i)$ llamando a $\tan^{-1}{\frac{y_i}{x_i}}$ . Para ordenar los puntos en sentido antihorario, simplemente ordenamos los puntos según su argumento de menor a mayor.

El problema, convenientemente, nos pide que los puntos ordenados empiecen en el 3.er cuadrante y terminen en el 2.º cuadrante, lo cual coincide con las características de la función $\tan^{-1}$ de la librería, donde los puntos del 3.er y 4.º cuadrante tienen ángulos negativos y los del 1.er y 2.º cuadrante tienen ángulos positivos.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N \cdot M(N))$ , donde $M(N)$ es la complejidad de computar $\tan^{-1}{N}$

C++


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct Point {
	ll x;
	ll y;
};
 
int main() {
	int n;
	cin >> n;
	vector<Point> points(n);
	for (int i = 0; i < n; i++) { cin >> points[i].x >> points[i].y; }
 
	// sort counterclockwise
	auto cmp = [](const Point &a, const Point &b) {
		return atan2l(a.y, a.x) < atan2l(b.y, b.x);
	};
	sort(points.begin(), points.end(), cmp);
 
	for (int i = 0; i < n; i++) { cout << points[i].x << " " << points[i].y << "\n"; }
}