me pidieron siguiente pregunta en una entrevista reciente:Encontrar el punto de intersección más cercano en el plan
Que suponga que tiene, después de cuadrícula en el sistema de coordenadas cartesianas (cuadrante I).
o - x - x - x - o
| | | | |
x - x - x - o - x
| | | | |
x - o - o - x - x
where, o => person at intersection and x => no person at intersection
class Point {
int x;
int y;
boolean hasPerson;
}
Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {
}
Implementar una rutina donde da una lista de personas de localización (puntos), encontrar un lugar (punto) de tal manera que es punto más cercano a todo punto dado.
¿Cómo resolvería este problema?
1) El enfoque es k-d árbol, pero ¿conoce alguna otra solución?
Si el "punto más cercano a todos los puntos dados" significa la suma mínima de distancias, entonces mira http://en.wikipedia.org/wiki/Geometric_median – MBo