¿Cuál es el mejor algoritmo para encontrar el número máximo de puntos que pueden estar contenidos en un rectángulo de área fija, pero no en lados fijos?

Answer 1

¿Cuál es el “tamaño de un punto”? Un punto matemático tiene un tamaño cero y puede empaquetar un número infinito incontable de puntos a lo largo de un subintervalo continuo a lo largo de un eje, y mucho menos que tenga dos o más dimensiones …

¿Qué otras limitaciones tiene tu problema? ¿Son todas las coordenadas de sus puntos enteros?

De todos modos, si el problema ha sido ligeramente diferente, así: la longitud total de todos los lados es fija, de lo que se obtiene el área máxima si el rectángulo es un cuadrado.

Aunque no entiendo completamente su problema, probablemente “cuadrado” es el resultado correcto. Ahora, ¿no sé que puedo responder preguntas correctamente, incluso si no las entiendo? Un pequeño problema es que no parece estar interesado en qué tipo de rectángulo (como un cuadrado o no), sino en la cantidad de puntos . Bueno, entonces explica tu problema para que los lectores puedan entenderlo … ¿Pero quieres apostar? Obtiene su número máximo de puntos (si eso tiene sentido), en caso de que su rectángulo sea un cuadrado …

Puedes hacerlo simplemente pensando lateralmente. Solo hay un rectángulo que es especial de alguna manera: un cuadrado. Todos los demás son solo rectángulos arbitrarios. Entonces, ¿por qué alguno de estos tiene la propiedad especial de poder contener un máximo de lo que sea? Entonces también podría rotar dicha solución 90 grados y tendrá otra solución …

Por cierto, en general, la resolución de un problema comienza con la comprensión de cuál es el problema. Por su redacción, tengo la sensación de que aún no has pasado esa etapa. No es de extrañar que no pueda responder una pregunta, si no sabe de qué se trata la pregunta … Una vez que haya aclarado eso, la respuesta podría volverse obvia (o es obvio que la pregunta en sí misma es ridícula).

Answer 2

Supongamos que P [i] es nuestra matriz original de puntos. Ordene los puntos por las coordenadas x que forman la matriz A [i], y por la coordenada y en la matriz B [i]. Ambos deberían ser O ( n log n ) complejidad.

Si V es el área deseada, entonces (x, y) es la coordenada inferior izquierda, la coordenada superior izquierda (u, v) satisface (ux) * (vy) = V, definiendo una hipérbola. Recorra A [i], B [i] descartando todos los puntos con x-coord menor que x, y-coord menor que y o (ux) * (vy)> V, forme matrices C, D a partir de estos. Considere un punto que se mueve a lo largo de la hipérbola desde la parte superior izquierda a la parte inferior derecha. Esto define un rectángulo. A medida que se mueve, el número de puntos aumentará en uno cada vez que el borde derecho pase un punto, y disminuirá en uno cada vez que el borde superior pase un punto.

recuento de funciones (x, y, V) {
C = []; D = [];
para (p en A) {
if (px> x && py> y && (px-x) * (py-y) C.add (p);
}
para (p en B) {
if (px> x && py> y && (px-x) * (py-y)
D.add (p);
}
D.reverse (); // Queremos las coordenadas y en orden decreciente
j = 0; // índice para la matriz D
cuenta = 0; // recuento actual de puntos
maxcount = 0; // número máximo de puntos
para (p en C) {// creciente x coord
++ recuento; // nuestro punto actual agregado
arriba = y + V / (px-x);
while (D [j]> arriba) {
-contar; // perdió uno de los primeros puestos
++ j;
}
if (recuento> maxcount) maxcount = contar;
}
}

Desea llamar al código anterior, para cada punto. El orden de la función es un poco más que O (N) pero ciertamente menor que O (N ^ 2), lo que hace que el algoritmo resultante sea menor que O (N ^ 3).