Задача: Max Points on a Line
Горячее солнце осветило спальню. Яркие лучи пробежали по лицу старшего разработчика Василия. «Ещё пять минуточек», — хитрая надежда проскользнула в голове Васи, и он растянулся в довольной улыбке, пока неожиданно не осознал, что проспал. Какой уже день подряд он просыпался с мобильным телефоном в руке и пропущенным будильником. Всё это дико раздражало, но хитрый организм не воспринимал проблемы Василия всерьёз и лично принимал решение об отключении будильника раньше, чем Вася успевал понять, что происходит. Разбираться с этим времени не было, вот-вот уже должен был начаться очередной важный митинг. Уже целую неделю команда не может определиться, где лучше располагать очень важную кнопку. Необходимость личного присутствия на митинге Василию была не до конца понятна, как и сама причина такого мучительного выбора. Но, как бэкенд разработчик, он постоянно должен был подтверждать: «Если кнопка будет располагаться на десять пикселей правее, то это не поломает бэкенд».
Василий всё больше понимал, что времени на саму разработку у него не хватает, поэтому всё чаще листал LinkedIn, посещал митапы и играл в настольные игры с незнакомыми людьми в поисках новых разработчиков в свою команду. Нашей редакции удалось получить одну из задач, которую Вася предлагает в качестве тестовой. Поэтому предлагаем вместе разобраться с решением, вдруг Василий напишет и тебе!
Постановка задачи. Пусть есть множество точек на плоскости. Необходимо найти прямую, проходящую через наибольшее количество точек.
Полную реализацию на C# можно посмотреть на GitHub проекта coding-interview.
Поскольку прямых на плоскости бесконечное множество, то и поиск ответа может занять вечность, а твой интервьюер очень занятой человек, ему ещё участвовать в командном митинге о выборе имени и цвета кнопки. Поэтому попробуем ускориться и оптимизировать подход.
Ограничим множество прямых, которые потенциально могут являться ответом. Если множество точек пустое, то любая прямая будет являться ответом. Например, можно возвращать прямую, проходящую через центр координат.
Прямая однозначно задаётся двумя различными точками, поэтому будем перебирать все возможные пары различных точек, строить по ним прямую, и проверять принадлежность точек этой прямой.
Мы работаем с вещественными координатами, поэтому сравнение точек будет осуществляться с какой-то точностью, отсюда и название методов: AllPointsAreAlmostEqual, IsAlmostEqual и так далее. Опустим пока что реализацию геометрических методов и остановимся на построении тела алгоритма:
public (Line<double> Line, int PointsCount) FindLine(List<Point<double>> points)
{
if (AllPointsAreAlmostEqual(points))
{
var point = points.FirstOrDefault() ?? new Point<double>(0, 0);
var line = LinesFactory.BuildAnyLine(point);
return (Line: line, PointsCount: points.Count);
}
var maxPointsOnLineCount = 0;
Line<double> bestLine = new Line<double>(1, 0, 0);
foreach (var firstPoint in points)
{
foreach (var secondPoint in points)
{
if (secondPoint.IsAlmostEqual(firstPoint))
{
continue;
}
var line = LinesFactory.BuildLine(firstPoint, secondPoint);
var pointsOnLineCount = points.Count((p) => line.AlmostContains(p));
if (pointsOnLineCount > maxPointsOnLineCount)
{
maxPointsOnLineCount = pointsOnLineCount;
bestLine = line;
}
}
}
return (Line: bestLine, PointsCount: maxPointsOnLineCount);
}
private bool AllPointsAreAlmostEqual(List<Point<double>> points)
{
var p1 = points.FirstOrDefault();
return points.All((p) => p.IsAlmostEqual(p1));
}Данный алгоритм имеет кубическую сложность O(n^3): нам необходимо перебрать все возможные пары точек O(n^2), построить по ним прямую O(1) и проверить принадлежность точек этой прямой O(n).
Рассмотрим случай, когда три точки лежат на одной прямой:
Зафиксируем точку A в качестве первой точки прямой. Наш реализованный алгоритм сначала построит прямую по паре точек (A, B) и проверит принадлежность точек данной прямой, а потом для пары точек (A, C). Но это одна и та же прямая! Более того, если пара точек (A, B) и пара точек (A, C) формируют одну и ту же прямую, то это значит, что все три точки лежат на этой прямой.
Так как мы зафиксировали первую точку прямой A, то мы можем утверждать, что все прямые проходят через эту точку, а значит их можно однозначно задать вектором направления прямой. Более того, коллинеарные векторы будут соответствовать одной и той же прямой:
Таким образом, для каждой зафиксированной точки необходимо найти направление (какой-то нормализованный вектор), которому коллинеарно наибольшее количество векторов, формируемых парой различных точек.
Временно введём ограничение на координаты точек. Пусть все наши точки имеют только целочисленные координаты. Тогда координаты всех направляющих векторов также будут целочисленными. Тогда для нормализации координат разделим обе координаты на их наибольший общий делитель. Этот вектор не является нормализованным в математическом смысле, но позволяет использовать его как эталон для всех коллинеарных данному вектору векторов. Например, вектора (4, 2) и (-2, -1) преобразуются к вектору (2, 1).
На основе сказанного выше построим улучшенное решение для целочисленных координат. Зададим тело основного метода. Для каждой зафиксированной точки будем находить направление с наибольшим количеством коллинеарных векторов:
public (Line<long> line, int PointsCount) FindLineFast(List<Point<long>> points)
{
(var origin, var direction, var pointsCount) = FindVectorFast(points);
var line = LinesFactory.BuildLine(origin, direction);
return (line, pointsCount);
}
private (Point<long> Origin, Vector<long> Direction, int PointsCount) FindVectorFast(
List<Point<long>> points)
{
if (AllPointsAreEqual(points))
{
var origin = points.FirstOrDefault() ?? new Point<long>(0, 0);
var direction = new Vector<long>(1, 1);
return (Origin: origin, Direction: direction, PointsCount: points.Count);
}
Point<long> bestOrigin = new Point<long>(0, 0);
Vector<long> bestDirection = new Vector<long>(1, 1);
var maxPointsCount = 0;
foreach (var origin in points)
{
(var direction, var pointsCount) = FindDirectionWithMaxPointsCount(origin, points);
if (pointsCount > maxPointsCount)
{
bestOrigin = origin;
bestDirection = direction;
maxPointsCount = pointsCount;
}
}
return (Origin: bestOrigin, Direction: bestDirection, PointsCount: maxPointsCount);
}
private bool AllPointsAreEqual(List<Point<long>> points)
{
var p1 = points.FirstOrDefault();
return points.All((p) => p.IsEqual(p1));
}Реализуем алгоритм нахождения наилучшего вектора направления для зафиксированной точки:
private (Vector<long> Direction, int PointsCount) FindDirectionWithMaxPointsCount(
Point<long> origin,
List<Point<long>> points)
{
int originDuplicates = 0;
var pointsCountPerDirection = new Dictionary<long, Dictionary<long, int>>();
int maxPointsCount = 0;
Vector<long> bestDirection = new Vector<long>(1, 1);
foreach (var linePoint in points)
{
if (linePoint.IsEqual(origin))
{
++originDuplicates;
continue;
}
var direction = NormalizeDirection(
VectorsFactory.BuildVector(origin, linePoint)
);
var pointsCount = AddDirectionAndGetPointsCount(
pointsCountPerDirection,
direction
);
if (pointsCount > maxPointsCount)
{
maxPointsCount = pointsCount;
bestDirection = direction;
}
}
return (Direction: bestDirection, PointsCount: maxPointsCount + originDuplicates);
}Реализуем построение нормализованного вектора и подсчёт количества коллинеарных ему векторов. Для этого создадим ассоциативный двумерный массив, где в качестве ключей будут выступать координаты (X, Y) нормализованного вектора, а в качестве значений — количество векторов, коллинеарных данному вектору:
private Vector<long> NormalizeDirection(Vector<long> direction)
{
long gcdValue = Arithmetic.GCD(direction.X, direction.Y);
return new Vector<long>(direction.X / gcdValue, direction.Y / gcdValue);
}
private int AddDirectionAndGetPointsCount(
Dictionary<long, Dictionary<long, int>> directionsCountPerOrigin,
Vector<long> direction)
{
if (!directionsCountPerOrigin.TryGetValue(direction.X, out var fixedXCounts))
{
fixedXCounts = new Dictionary<long, int>();
directionsCountPerOrigin[direction.X] = fixedXCounts;
}
if (!fixedXCounts.TryGetValue(direction.Y, out var count))
{
count = 0;
}
fixedXCounts[direction.Y] = count + 1;
return count + 1;
}Таким образом мы получили алгоритм со сложностью O(n^2), где для каждой зафиксированной точки O(n) находится наилучший вектор направления O(n).
Важным замечанием к алгоритму выше является реализация расчёта наибольшего общего делителя (GCD). Результирующий делитель также выполнит поворот вектора в нужную четверть.
public static long GCD(long x, long y)
{
long cx = Math.Abs(x);
long cy = Math.Abs(y);
while (cx != 0)
{
(cx, cy) = (cy % cx, cx);
}
return (x, y) switch
{
(long xv, _) when xv < 0 => -cy,
(0, long yv) when yv < 0 => -cy,
_ => cy
};
}Алгоритм выше предназначен для работы с целочисленными координатами. Предположим, что все наши координаты заданы с какой-то точность digitsPrecision (количество значимых цифр после запятой). Тогда мы можем выполнить расчёты, домножив все координаты на multiplier = 10 ^ digitsPrecision, и свести решение задачи к случаю, описанному выше. А результирующий ответ получим обратным преобразованием (делением на multiplier):
public (Line<double> line, int PointsCount) FindLineFast(
List<Point<double>> points,
int digitsPrecision = DefaultDigitsPrecision)
{
double multiplier = Math.Pow(10, digitsPrecision);
var longPoints = points.Select((p) => new Point<long>(
Convert.ToInt64(Math.Round(p.X * multiplier)),
Convert.ToInt64(Math.Round(p.Y * multiplier))
)).ToList();
(var longOrigin, var longDirection, var pointsCount) = FindVectorFast(longPoints);
var origin = new Point<double>(
longOrigin.X / multiplier,
longOrigin.Y / multiplier
);
var direction = new Vector<double>(
longDirection.X / multiplier,
longDirection.Y / multiplier
);
return (LinesFactory.BuildLine(origin, direction), pointsCount);
}На этом всё, а тебе, дорогой читатель, предлагаю ознакомиться с другими разборами задач, которые могут попадаться на технических собеседованиях. До скорых встреч!
