Всем привет в этом видео Я разберу шестую задачу из текущего алгоритмического отборочного контеста на стажировку в теньков Но прежде чем начать предлагаю подписаться на мой Telegram канал именно там Я разберу все остальные задачи с этого отбора помимо этого там я также разбираю задачи со вступительных контеста в другие компании Яндекс Ozone контур Тиньков выкладываю решение интересных задач разборы наиболее важных тем для собеседований и многое другое Также подписывайтесь на этот YouTube канал ставьте лайки делитесь своим мнением в комментариях ну а мы начинаем шестая задача выглядит так в этом году главой флот нди является Егор всего во флот
деи проживает н людей каждый в своём доме ИТ и дом находится в целочисленной точке X ИТ Y и т Егор может выделить некоторые тройки людей требуется лишь чтобы каждый человек относился не более чем к одной тройке тройка людей считается счастливой если треугольник образованный их томами является не выраж денним то есть три дома не находятся на одной прямой Помогите Егор определить какого максимального количества счастливых троек можно добиться во флот нди соответственно входные данные выглядят следующим образом у нас первая строка содержит число n количество жителей во флот нди не превышающая от 300 и соответственно каждая следующих строчек
содержит число X ИТ Y ИТ координаты дома где проживает ИТ человек и нам нужно соответственно вывести одно число максимальное количество счастливых троек которого можно добиться во флот нде Давайте немножко формализуются получается что у нас есть у нас есть какой-то набор точек на координатной прямой и собственно Мы хотим соединить эти точки объединить их В треугольники Да причём получается каждая точка должна принадлежать максимум одному треугольнику такая точка будет Вот такая вот то есть объединить эти точки В треугольнике причём сделать так чтобы количество треугольников которое у нас получилось было максимально замечательно Хорошо давайте Теперь попробуем понять А собственно
почему мы не можем все точки объединить треугольники да то есть после того как мы всё пообъектный [музыка] треугольники выраженный треугольник это просто вот прямая на кото вот три точки расположе получается получается что в кон после соединения всех точек во всевозможные треугольники конструкция будет выглядеть следующим образом какие-то треугольники соответственно и получается оставшиеся точки будут лежать все на одной прямой То есть через них можно будет провести прямую Да соответственно больше никакую пару точек точнее больше никакую тройку точек мы больше не сможем объединить в треугольник хорошо то есть получается Если мы хотим максимизировать число получившихся треугольников есть мым
максимизировать заст точек Это значит что мы хотим минимизировать число оставшихся точек то есть в конце после всевозможного соединения Мы хотим чтобы осталось минимальное число не Соединённых точек то есть минимальное число точек лежащих на одной прямой и отсюда вытекает такой вот несложный жадный алгоритм давайте рассмотрим вообще все возможные прямые Да соответственно на которых лежат точки А дальше на каждом шае будем выбирать пря на которой находится максимальное число точек далее соответственно удалим две точки с этой прямой возьмём третью точку не лежащую на этой прямой из них образуем треугольник и собственно эти точки ВС задействованы мы их больше
не рассматриваем и продолжаем собственно интерактивном дальше Давайте на каком-нибудь примере это можно как-нибудь Покажу значит допустим вот такие три точки у нас будут какая-нибудь такая точка Вот такая точка Вот такая тока такая точка значит давайте построим все прямые которые собственно у нас получаются здесь у нас будет прямая вот здесь у нас будет прямая Извиняюсь за качество конечно так здесь прямая здесь прямая собственно Конечно можно здесь прямые провести собственно между каждой парой точек у нас будет прямая так вот здесь прямая вот здесь прямая Ну кажется вот эти вот можно уже не проводить Да каждая прямая будеть
из двух точек хорошо видим что значит первый шаг алгоритма выбираем прямую на которой максимальное число точек видим что это у нас вот эта прямая вот у нас Аче точки на ней лежат Давайте возьмём какие-нибудь две точки произвольные допустим вот эти возьмём любую точку не лежащую на этой прямой например вот эту образуем из них треугольник и про них забудем снова теперь нам нужно опять выбираем прямую на которой лежит максимальное число точек Обратите внимание что теперь у нас на любо жать не более ДХ точек Ну точнее только две точки ка рандомную прям вот эту вот да вот
такая вот прямая берм две точки с неё берм третью точку этой прямой Соединяем их треугольника про них забываем и переходим к следующему шагу в конце концов остаётся одна единствен точка для неё нужно будет повторять пока у нас не останется какая-то прямая содержащая все оставшиеся точки почему это работает ну потому что смотрите потому что мы хотим чтобы в конце концов У нас осталась Прямая на которой будет лежать минимальное число точек на каждом шаге жано алгоритма мы минимизируем число точек на прямой на которой в текущем момен расположено максимальное точек есть кажы мешаем маль пря в конце концов
после всех действий мы как раз таки достигнем того что в конце у нас останется Прямая на которой будет расположено минимальное число точек за сколько это будет работать И вообще как это реализовывать Ну во-первых давайте да немножко поясним как это будем собственно реализовывать в коде во-первых Давайте поймём чем зада каждая прямая вопервых можем всевозможных у нас может получиться ну максимум прямых получится что-то типа порядка N к Почему Потому что у нас есть замечательная аксиома или теорема Да что через любые две точки можно провести прямую причём только одну поэтому каждая пара точек будет задавать свою прямую соответственно
Как найти и задать вообще саму прямую Представьте У нас есть пара точек x22 И мы хотим посмотреть как будет задаваться прямая проходящая через эти две точки каждая прямая задаётся числом K коэффициентом наклоны и B Соответственно смещением по А собственно её смещением Да смотрим пишем уравнение прямой y1 будет равняться kx1 + B далее соответственно y2 - это у нас тот же самый K X2 + B Да эти д точки принадлежат одно и тоже прямой нам нужно получается найти из этой системы уравнения K и B вычтем одно уравнение из другого отм буде ра y1 -21 -2 мы
нашли поэтому это можно поставить например в первое уравнение системы или во второе я поставлю в первое отсюда мы найдём как раз таки это получается y1 ми1 поставляем собственно получаем формулу для коэ да пара чисел K и B мы можем задать любую прямую Хорошо тогда давайте заведём какой-нибудь Map да то есть Map отображение словарь где ключами будут выступать соответственно вот эти вот пары чисел K и B задающие прямую а в соответствии им поставим например какое-нибудь множество и соответственно точек то есть получается мы каждой прямой Составляем все точки лежащие на этой прямой соответственно за время у от
N ква мы можем проверить все возможные прямые и распределить точки по соответственно этим прямым Обратите внимание что Через каждую точку может проходить несколько прямых Да но через каждую пару только одна Замечательно Это мы с вами сделали теперь что будем делать собственно теперь остатся максимум раз повторить арим Почему Мараз потому что на каждом шаге будем удалять минимум три точки сам на ра повторяться будет порядок поэтому примерно раз что будем делать мы будем итерироваться по нашему мапу получившемуся смотреть брать соответственно тот ма у которого максимальный размер этого соответствующего Сета да льну прямую собственно с неё забираем две
точки потом мся по мапу забираем какую-нибудь точку не лежащую на этой прямой собственно говорим что это теперь треугольник и снова проходим по этому Мабу и собственно очищаем удаляем вхождение всех этих трёх точек во все прямые в которые они до этого входили собственно получается что мы n раз итеру по всем прямым получается В итоге решение что-то типа о от N вку обращаю внимание на ограничение и он у нас не больше 3 Поэтому такая сложность Вполне себе приемлемая собственно она такое решение действительно оптимально для этой задачи Конечно можно придумать ещё более оптимальное решение например использовать для нахождения
максимального числа вхождений можно использовать какого-нибудь дерево отрезка как-то модифицировать да то есть э пере то пр вот конечно это всё можно добавить можно сделать более оптимальным Однако у нас это решение уже работает за N в третьей вот N третьей здесь Вполне себе вписывается в ограничение по времени поэтому наверное нет смысла как-то пытаться улучшать оно здесь уже заходит собственно и на этом наверное можно подвести итог идейной части и собственно реализовать эту задачу уже программно вот так вот выглядит программное решение нашей задачи и Давайте разбираться с ним подробнее значит здесь я определяю функцию getline которая по двум
заданным точкам то есть по четырём координатам Да находит соответственно коэффициент наклона прямой проходящей через эти две точки и собственно её смещение Вот теперь давайте перейдём собственно к основной части значит задаётся число n задаётся массив из N пар где каждая ИТ пара содержит два числа X Y координату заданной точки да соответственно считываем этот массив теперь объявляем наше отображение кото уже обсуждали в идейной части Однако здесь обратите большое внимание Почему Потому что здесь я использую структуру данных Map в c+ Plus все операции спом работают за о от логарифма N и поэтому чтобы не дополнять Да чтобы не
добавлять лишний логарифм в асимптотику вашего решения лучше избавляться от этого Map использовать например unordered Map Или допустим каждой прямой задать там какой-то числовой код и Собственно уже работать с ним Да поэтому здесь просто написал для удобства Однако будьте внимательны лучше этот логарифм лишние восем точек не добавлять Вот например в питоне Да у нас там словарь - это не упорядоченное отображение поэтому там такой проблемы собственно не возникнет супер получается это отображение будет каждому каждой прямой Да собственно которая определяется двумя числами задавать множество из собственно индексов точек лежащих на этой прямой индексы будут соответственно из этого массива
замечательно Теперь давайте собственно эти прямые построим перебираем все возможные пары точек проверяем соответственно Да заводим пару из двух значений типа dou собственно где будем хранить коэфициент наклона и смещение нашей прямой теперь Значит у нас есть один очень Особый случай если у нас две точки имеют одинаковые X координаты и различные Y координаты Что это значит Значит просто вертикальная прямая Да у вертикальной прямой собственно разность между иксами будет нулевая то есть грубо говоря можно сказать что K в данном случае равняться будет бесконечности вот чтобы не делить на ноль и не допускать такую ошибку мы собственно в таком
вот виде зададим нашу прямую Ну а иначе если соответственно X координаты У них различные то с помощью функции getl мы можем посчитать соответственно и коэффициент наклона и смещение этой прямой Ну соответственно в наше отображение просто кладём индекс и индекс G да то есть э две точки лежат на одной прямой задаваемой соответствующими числами и парой чисел замечательно теперь собственно будем считать ответ задаём переменную А в которой будем собственно ответ хранить а далее делаем не более чем шагов на самом деле в реальности мы сделаем не больше чем N шагов Да ну вот собственно так тоже можно этом
длям пр расположено максимальное число точек Давайте собственно это количество изначально зададим нулевым нулём инициализирует если соответственно какой-то прямой в текущем варианте лежит меньше двух точек да то есть либо одна точка Ну в данном случае одна точка на самом деле то соответственно уже непрямая Да поэтому мы можем по соответствующему ключу по паре иб просто отчислить значение гово что ни одной точки на этой прямой не лежит потому что это уже не прямая да щ одной точки далее Просто каждый раз обновляем размер да сравниваем переменную Z с количеством точек лежащих на прямой если оказывается Так что у нас
не существует ни одной прямой то очевидно Больше никаких действий проворачивать не надо больше никакой треугольник мы с получить не можем Поэтому просто заканчиваем выполнение этого цикла далее если мы например нашли прямую на которой жит две и более точки собственно теперь нашли собственно максимальное чество точек на прямой теперь нам нужно собственно выцепить эти две точки и соответственно найти что же за прямая такая значит Ируся по прямой если оказ так что это прямой лежит то самое максимальное число точек что мы делаем мы собственно кладём первую точку в пару Да собственно индекс это точки Обратите внимание что здесь
работаем СМИ с индексами собственно удаляем с этой прямой ту точку берём ещё одну точку кладём вторую позицию в пару Вот совестном и наклона и собственно смещение у этой прямой в переменную Да нужно нужно уметь различать С какой прямой мы забрали две точки собственно и заканчиваем выполнение этого цикла То есть сейчас мы вычли две точки лежащие на прямой с максимальным числом точек собственно теперь нам нужно в соответствие им поставить ещё одну точку да взять третью точку чтобы потом образовать треугольник причём эта точка не должна лежать на той же самой прямой собственно для этого мы использовали дополнительную
переменную Давайте скажем что индекс точки знача ра ми1 Далее мся по всем прямым если у нас собственно получаем Като другую прямую Да равно и соответственно на этой прямой лежит какая-то точка то Соответственно что мы делаем соответственно мы а кладём индекс этой точки в переменную и заканчиваем наш циклы Если же больше никаких прямых кроме нашей прямой больше не существует то есть остал по-прежнему равно миди то никах действи больше делать не надо можно просто закончить выполнение основного цикла Ну а иначе мы удаляем соответственно эти три точки из всех прямых которым они могли принадлежать сто проходим се ещё
раз по всем прямым собственно удаляем с каждой прямой если это нужно все эти точки собственно если опять же на какой-то прямой оказалось меньше двух точек то это больше не прямая мы собственно её просто очищаем ну и АС увеличиваем на единичку мы нашли новую тройку точек ну в конце нужно просто вывести АНС да такой код на ством примере в условии даёт действительно правильно правильное значение вот собственно вот так вот будет выглядеть примерно наше решение опять же реализация может зависеть от вас да а опять же вы можете как-то по-другому это реализовывать на самом деле Лучше бы допустим
тот же самый Map описать по-другому вот однако я здесь вот привёл такой вот удобный вариант для реализации пожалуйста уже адаптируйся конкретно это решение будет работать что-то типа за N но Log N Да но однако Да если мы от мапа избавимся то будет уже чистый N поэтому пожалуйста ещё раз напоминание учитывайте это
