Maximum Number of Darts Inside of a Circular Dartboard

Explicación

La idea general es la siguiente: podemos intentar hallar la respuesta colocando el borde del círculo sobre cada punto, y luego barrer —o rotar— el círculo alrededor del punto para ver el máximo número de puntos que pueden quedar dentro del círculo. La imagen de abajo muestra cómo funciona el barrido:

angular-sweep

El barrido alrededor del punto $p$ se puede hacer en $\mathcal{O}(N \cdot \log{N})$ calculando para cada punto el ángulo de entrada y de salida del círculo. Después recorremos el arreglo ordenado de ángulos mientras llevamos los puntos activos, es decir, los puntos que yacen dentro del círculo. Los ángulos considerados serán relativos al centro del círculo. Analicemos cómo hallar el ángulo de entrada para un punto:

angular-sweep

$O$ - centro del círculo; $Q$ - punto arbitrario incluido en la lista de puntos; $r$ - radio del círculo; $a, b, \alpha$ - ángulos

Expresaremos los valores de los ángulos en radianes. El ángulo de entrada al círculo en este caso es $\alpha$ que se puede expresar como: $\alpha = b - a$ . El ángulo $a$ está justo encima del eje x, así que es simplemente $\arctg$ . Consideremos que $b=\angle{QPO}$ es un ángulo en el triángulo rectángulo $\triangle QPL$ , donde $L$ es el punto diametralmente opuesto de $P$ en el círculo, por lo tanto $\angle{PQL}=90\degree$ . En este caso, sabiendo que $PL=2 \cdot r$ —diámetro— y $PQ=\texttt{dist}(P,Q)$ , el ángulo $B$ se puede expresar convenientemente como $\arccos$ . En consecuencia, los ángulos $a, b$ tienen las siguientes fórmulas:

a=\arctg{\frac{Q_y-P_y}{Q_x-P_x}}\\ b=\arccos{\frac{\texttt{dist}(P,Q)}{2 \cdot r}}

Ahora que sabemos cómo hallar el ángulo de entrada, será más fácil hallar el ángulo de salida. Con las mismas notaciones que el anterior — $a, b$ con las mismas fórmulas— consideremos esto:

angular-sweep-exit

$O$ - centro del círculo; $Q$ - punto arbitrario incluido en la lista de puntos; $r$ - radio del círculo; $a, b, \alpha$ - ángulos

Se puede observar que: $\beta = a + b$ .

Este algoritmo se conoce como barrido angular (angular sweep) o problema de cubrimiento parcial de disco.

Implementación

Complejidad temporal: $\mathcal{O}(N^2 \cdot \log{N})$

C++Python


class Solution {
  public:
	int numPoints(vector<vector<int>> &darts, int r) {
		vector<vector<double>> dist(darts.size(), vector<double>(darts.size()));
		// Compute the distance between points
		for (int i = 0; i < darts.size(); i++) {
			for (int j = i + 1; j < darts.size(); j++) {
				int dx = darts[i][0] - darts[j][0];
				int dy = darts[i][1] - darts[j][1];
				dist[i][j] = dist[j][i] = sqrt(dx * dx + dy * dy);
			}
		}
 
		int ans = 1;
		for (int i = 0; i < darts.size(); i++) {
			// Store the angles of other points relative to darts[i]
			vector<pair<double, bool>> angles;
			for (int j = 0; j < darts.size(); j++) {
				// Continue if it's the same point or if it lies outside any
				// circle
				if (i == j || dist[i][j] > 2 * r) { continue; }
				double a = atan2(darts[j][1] - darts[i][1], darts[j][0] - darts[i][0]);
				double b = acos(dist[i][j] / (2.0 * r));
				double alpha = a - b, beta = a + b;
				// The angle at which the point enters the circle
				angles.push_back({alpha, false});
				// The angle at which the point leaves the circle
				angles.push_back({beta, true});
			}
 
			// Sort all the angles
			sort(angles.begin(), angles.end());
 
			int active_points = 1;
			for (const pair<double, int> &angle : angles) {
				if (!angle.second) {
					active_points++;
				} else {
					active_points--;
				}
				ans = max(ans, active_points);
			}
		}
 
		return ans;
	}
};


class Solution:
	def numPoints(self, darts: List[List[int]], r: int) -> int:
		# Compute the distances between all pairs of points
		dist = [[0] * len(darts) for _ in range(len(darts))]
		for i in range(len(darts)):
			for j in range(i + 1, len(darts)):
				dx = darts[i][0] - darts[j][0]
				dy = darts[i][1] - darts[j][1]
				dist[i][j] = dist[j][i] = math.sqrt(dx * dx + dy * dy)
 
		ans = 1
		for i in range(len(darts)):
			# Store the angles of other points relative to darts[i]
			angles = []
			for j in range(len(darts)):
				# Continue if it's the same point or if it lies outside any circle
				if i == j or dist[i][j] > 2 * r:
					continue
 
				a = math.atan2(darts[j][1] - darts[i][1], darts[j][0] - darts[i][0])
				b = math.acos(dist[i][j] / (2.0 * r))
				alpha = a - b
				beta = a + b
 
				# The angle at which the point enters the circle
				angles.append((alpha, False))
				# The angle at which the point leaves the circle
				angles.append((beta, True))
 
			# Sort all the angles
			angles.sort()
 
			active_points = 1
			for angle, is_exit in angles:
				active_points += -1 if is_exit else 1
				ans = max(ans, active_points)
 
		return ans