Line Segment Distance

Explicación

Distancia de un punto a un segmento

Antes de resolver para dos segmentos, hay que entender cómo hallar la distancia más corta de un solo punto $P$ a un segmento $AB$ .

Si proyectamos el punto $P$ sobre la recta infinita que contiene a $AB$ , la posición de la proyección se puede describir con un escalar $t$ . Si expresamos la recta como $A + t \cdot \vec{AB}$ , podemos calcular $t$ usando el producto punto:

t = \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|^2}

Este escalar $t$ nos dice dónde está el punto más cercano respecto del segmento:

$t \le 0$ : La proyección cae antes de $A$ . El punto más cercano del segmento es el extremo $A$ .
$t \ge 1$ : La proyección cae después de $B$ . El punto más cercano del segmento es el extremo $B$ .
$0 < t < 1$ : La proyección cae estrictamente entre $A$ y $B$ . El punto más cercano es la proyección misma: $A + t \cdot \vec{AB}$ .

La distancia es entonces simplemente la distancia euclidiana entre $P$ y este punto más cercano.

Distancia entre segmentos

Ahora consideremos dos segmentos, $S_1$ y $S_2$ . Podemos visualizar la relación entre ellos usando un proceso iterativo:

Elegir un punto arbitrario $P_1$ en el segmento $S_1$ .
Hallar el punto $P_2$ en el segmento $S_2$ que está más cerca de $P_1$ .
Desde $P_2$ , hallar el punto $P_3$ en el segmento $S_1$ que está más cerca de $P_2$ .

Ahora, si $P_2=P_3$ , entonces los segmentos se intersectan. Así que la distancia más corta es 0. (Caso trivial)

En caso contrario, seguimos repitiendo el proceso hasta llegar a un punto donde $P_n$ , $P_{n+1}$ , $P_{n+2}$ , $P_{n+3}$ cumplen $P_n = P_{n+2}$ y $P_{n+1} = P_{n+3}$ . Esto significa que hemos alcanzado el último ciclo. Aquí podemos observar que siempre al menos uno de $P_n$ o $P_{n+1}$ es un extremo de un segmento.

Caso borde: esto puede NO ser cierto cuando los segmentos son paralelos. En ese caso, la distancia más corta se puede obtener de un conjunto de infinitos puntos que contiene al menos uno de los extremos.

Por lo tanto, para resolver el problema en cualquier caso, simplemente calculamos el mínimo de cuatro valores:

$\text{dist}(A, S_2)$
$\text{dist}(B, S_2)$
$\text{dist}(C, S_1)$
$\text{dist}(D, S_1)$

Demostración

¿Por qué vale esta observación?

Podemos formalizarla usando cálculo. La función de distancia $f(t, u)$ entre un punto de $S_1$ (parametrizado por $t$ ) y un punto de $S_2$ (parametrizado por $u$ ) es una función convexa sobre el dominio $[0, 1] \times [0, 1]$ .

Para una función convexa definida en un dominio cuadrado, el valor mínimo debe ocurrir o bien:

En un punto estacionario donde el gradiente es cero. Esto corresponde al caso en que los segmentos son paralelos (infinitos puntos estacionarios) o se intersectan (la distancia es 0).
En el borde del dominio.

Si las rectas son alabeadas (no paralelas y no se intersectan), no hay un punto estacionario con gradiente cero dentro del cuadrado. Así, el mínimo debe ocurrir en el borde del dominio $[0, 1] \times [0, 1]$ .

El borde de este dominio corresponde a $t=0$ , $t=1$ , $u=0$ o $u=1$ . Geométricamente, estos valores de los parámetros corresponden exactamente a los extremos de los segmentos.

Implementación

Complejidad temporal: $\mathcal{O}(1)$ por caso de prueba.

C++


 
#include <bits/stdc++.h>
using namespace std;
 
using T = double;
 
// BeginCodeSnip{Point Class}
struct Point {
	T x, y;
	Point operator-(const Point &other) const { return {x - other.x, y - other.y}; }
	Point operator+(const Point &other) const { return {x + other.x, y + other.y}; }
	Point operator*(T s) const { return {x * s, y * s}; }
 
	T dot(const Point &other) const { return x * other.x + y * other.y; }
	T cross(const Point &other) const { return x * other.y - y * other.x; }
 
	double dist() const { return hypot(x, y); }
	double dist2() const { return x * x + y * y; }  // Squared length
 
	// Check if vector is effectively zero (for degenerate segments)
	bool isZero() const { return abs(x) < 1e-9 && abs(y) < 1e-9; }
};
// EndCodeSnip
 
// BeginCodeSnip{Intersection}
// Checks if segment AB intersects segment CD using parametric equations
bool intersect(Point a, Point b, Point c, Point d) {
	Point ab = b - a;
	Point cd = d - c;
 
	// Cross product of direction vectors
	double cross_prod = cd.cross(ab);
 
	// If parallel or collinear, we treat as NO intersection for this problem.
	// The point-to-segment distance checks will handle the collinear cases.
	if (abs(cross_prod) < 1e-9) return false;
 
	// Solve for parameters t (for AB) and u (for CD) using the accepted logic
	// We derive these from the linear system: a + t*ab = c + u*cd
	double t = (ab.x * (c.y - a.y) + ab.y * (a.x - c.x)) / cross_prod;
	double u = (cd.x * (a.y - c.y) + cd.y * (c.x - a.x)) / -cross_prod;
 
	// Check if the intersection point lies strictly within both segments
	return (0.0 <= t && t <= 1.0) && (0.0 <= u && u <= 1.0);
}
// EndCodeSnip
 
// BeginCodeSnip{Distance Logic}
// Minimum distance from point P to segment AB
double distPointSegment(Point p, Point a, Point b) {
	Point ab = b - a;
 
	// Handle case where segment is just a single point
	if (ab.isZero()) return (p - a).dist();
 
	Point ap = p - a;
 
	// Project P onto the line containing AB.
	// t represents the position of the projection along the vector AB.
	double t = ap.dot(ab) / ab.dist2();
 
	if (t < 0.0) {
		// Closest point is A
		return (p - a).dist();
	} else if (t > 1.0) {
		// Closest point is B
		return (p - b).dist();
	} else {
		// Closest point is the projection itself
		Point projection = a + (ab * t);
		return (p - projection).dist();
	}
}
// EndCodeSnip
 
void solve() {
	Point a, b, c, d;
	cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
 
	// Case 1: Strict Intersection
	// If the segments strictly cross, distance is 0.
	if (intersect(a, b, c, d)) {
		cout << "0.00\n";
	}
	// Case 2: No Intersection
	// Includes parallel, collinear-disjoint, and skew cases.
	// The answer is the minimum distance from any endpoint to the other segment.
	else {
		double ans = min({distPointSegment(c, a, b), distPointSegment(d, a, b),
		                  distPointSegment(a, c, d), distPointSegment(b, c, d)});
		cout << ans << "\n";
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(2);
 
	int t;
	cin >> t;
	while (t--) { solve(); }
	return 0;
}