Нет, это не так. Смотрите вопрос preg_match и UTF-8 в PHP , например.
http://en.wikipedia.org/wiki/Closest_pair_of_points
Проблема может быть решена за время O (n log n) с использованием рекурсивного подхода «разделяй и властвуй», например, как следующим образом:
Я не могу сразу придумать более быструю альтернативу, чем метод грубой силы (хотя их должно быть много), но какой бы алгоритм вы ни выбрали , не вычисляйте расстояние между каждая точка. Если вам нужно сравнить расстояния, просто сравните квадратов расстояний, чтобы избежать дорогостоящего и полностью избыточного квадратного корня.
Вы можете извлечь ближайшую пару за линейное время из триангуляции Делоне и, наоборот, из диаграммы Вороного .
Для этой задачи существует стандартный алгоритм, вот его: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
А вот моя реализация этого алгоритма, извините, без комментариев:
static long distSq(Point a, Point b) {
return ((long) (a.x - b.x) * (long) (a.x - b.x) + (long) (a.y - b.y) * (long) (a.y - b.y));
}
static long ccw(Point p1, Point p2, Point p3) {
return (long) (p2.x - p1.x) * (long) (p3.y - p1.y) - (long) (p2.y - p1.y) * (long) (p3.x - p1.x);
}
static List<Point> convexHull(List<Point> P) {
if (P.size() < 3) {
//WTF
return null;
}
int k = 0;
for (int i = 0; i < P.size(); i++) {
if (P.get(i).y < P.get(k).y || (P.get(i).y == P.get(k).y && P.get(i).x < P.get(k).x)) {
k = i;
}
}
Collections.swap(P, k, P.size() - 1);
final Point o = P.get(P.size() - 1);
P.remove(P.size() - 1);
Collections.sort(P, new Comparator() {
public int compare(Object o1, Object o2) {
Point a = (Point) o1;
Point b = (Point) o2;
long t1 = (long) (a.y - o.y) * (long) (b.x - o.x) - (long) (a.x - o.x) * (long) (b.y - o.y);
if (t1 == 0) {
long tt = distSq(o, a);
tt -= distSq(o, b);
if (tt > 0) {
return 1;
} else if (tt < 0) {
return -1;
}
return 0;
}
if (t1 < 0) {
return -1;
}
return 1;
}
});
List<Point> hull = new ArrayList<Point>();
hull.add(o);
hull.add(P.get(0));
for (int i = 1; i < P.size(); i++) {
while (hull.size() >= 2 &&
ccw(hull.get(hull.size() - 2), hull.get(hull.size() - 1), P.get(i)) <= 0) {
hull.remove(hull.size() - 1);
}
hull.add(P.get(i));
}
return hull;
}
static long nearestPoints(List<Point> P, int l, int r) {
if (r - l == P.size()) {
Collections.sort(P, new Comparator() {
public int compare(Object o1, Object o2) {
int t = ((Point) o1).x - ((Point) o2).x;
if (t == 0) {
return ((Point) o1).y - ((Point) o2).y;
}
return t;
}
});
}
if (r - l <= 100) {
long ret = distSq(P.get(l), P.get(l + 1));
for (int i = l; i < r; i++) {
for (int j = i + 1; j < r; j++) {
ret = Math.min(ret, distSq(P.get(i), P.get(j)));
}
}
return ret;
}
int c = (l + r) / 2;
long lD = nearestPoints(P, l, c);
long lR = nearestPoints(P, c + 1, r);
long ret = Math.min(lD, lR);
Set<Point> set = new TreeSet<Point>(new Comparator<Point>() {
public int compare(Point o1, Point o2) {
int t = o1.y - o2.y;
if (t == 0) {
return o1.x - o2.x;
}
return t;
}
});
for (int i = l; i < r; i++) {
set.add(P.get(i));
}
int x = P.get(c).x;
double theta = Math.sqrt(ret);
Point[] Q = set.toArray(new Point[0]);
Point[] T = new Point[Q.length];
int pos = 0;
for (int i = 0; i < Q.length; i++) {
if (Q[i].x - x + 1 > theta) {
continue;
}
T[pos++] = Q[i];
}
for (int i = 0; i < pos; i++) {
for (int j = 1; j < 7 && i + j < pos; j++) {
ret = Math.min(ret, distSq(T[i], T[j + i]));
}
}
return ret;
}
Одна из возможностей состоит в том, чтобы отсортировать точки по их координатам X (или Y - неважно, какие, просто согласованность). Затем вы можете использовать это, чтобы исключить сравнения со многими другими точками. Когда вы смотрите на расстояние между точкой [i] и точкой [j], если только расстояние X больше, чем ваше текущее кратчайшее расстояние, тогда точка [j + 1] ... точка [N] может быть удалена как хорошо (при условии i
j , тогда удаляются точки [0] ... точка [i]).
Если ваши очки начинаются в качестве полярных координат вы можете использовать один и тот же вариант - отсортировать по расстоянию от начала координат, и если разница в расстоянии от начала координат больше, чем ваше текущее кратчайшее расстояние, вы можете удалить эту точку,