Сложная задача

До конца семестра осталось всего ничего, вот лично у шестой группы впереди всего одна практика и мы наконец-то решили раздать вам расчётно-графические задания по методам программирования! Авававав ававав выр авававыр языке математики авыавав! Вырвырвыр!

Так, это у нас Долбоёбов1. Долбоёбов... Так... Хмм... Сорок семь. Переписывайте.

На плоскости задано множество окружностей. Две окружности A и B назовём связанными, если они пересекаются либо существует третья окружность C заданного множества, связанная с A и B. Выбрать максимальное подмножество попарно не связанных друг с другом окружностей.

Хаааа, бодрячком, пацанчики! Чо-чо-опа нихуя! ЖЭСТЬ, НЕ ХУЯ НЕ ПОНЯТНО! ЛЕНЕЙКА ЭТО ВАЩЕ ПЕЗДЕЦ! Деман, читай Мураками! Расчётка по методам? Да я хуй клал на неё. Да я блядь условия даже не читал. Ты чо опух? Иди сюда нахуй! Ой, а завтра же сдавать :-( House/Eric Prydz/Pryda Records -> заменить, Vol Up, Vol Up, Win + K, #inclu, Ctrl+S... Так, чо решаем?

Хааа, ваще для лохов задача. Vol Up, Vol Up, Vol Up.

int circlesCross(circle circle1, circle circle2)
{
    float distanceX = circle1.x - circle2.x;
    float distanceY = circle1.y - circle2.y;
    float distanceBetweenCenters = sqrt(distanceX * distanceX + distanceY * distanceY);
    return (distanceBetweenCenters <= circle1.r + circle2.r);
}

Так, сейчас остались самые мелочи... Три окружности... Связные... Так, тут перебирать что ли? ПОДМНОЖЕСТВА??? Рекурсия что ли? Эмм, что-то есть явно проще и быстрее.

Два часа раздумий привели к теории графов. В самом деле, окружности — множество вершин, между ними ребро если они не связаны. Обычный просто неориентированный граф. Выделить максимальный полный подграф — и дело в шляпе. Так, где там методичка, в ней наверняка должен быть алгоритм...

Так, ничего тут нету. Даже упоминания о полном подграфе. На парах наверное это разбирают. Пусть разбирают, у нас Google есть. Ctrl+O, Ctr+L, «поиск максимального полного подграфа»... Таак, дело принимает интересный оборот. Максимально полный подграф называется кликой. Такого точно нет. Это материал второго семестра ящетаю. Безобразие. ФПМИ же.

Нашлось три алгоритма. Первый и самый эффективный в википедии — Брона-Кербоша. Какой-то он мутный, хер поймёшь. Второй семестр точно. Может что попроще есть. Да, вот тут целый курсач по этой теме! А они в середине курса задают. Как не стыдно. В курсаче алгоритм на паскале. Переменные транслитом, отступы как попало. Мудила ёбана блядь. Кто так пишет. Хуесос траханый. Уёбище свинорылое. Гондон. Пидор блядь. Так, проще, ещё проще. О, жежечка, комменты. Простейший алгоритм, выполнится за 2^k. Работает с матрицей смежности. 01:30. Отлично же! Берём, составляем матрицу. Программируем алгоритм. Ближе к концу понимаем, что не понимаем как выйти из рекурсии. Сука. Ладно, на сегодня достаточно.

10:45. Чёрт, через три часа это говно сдавать, а ещё ничего не готово! Так, графы тут явно не при чём, опять на ночь глядя себя умным решил почувствовать. Проще надо. Составить матрицу, вычеркнуть столбцы и строки с нулями не на диагоналях (окружность связана сама с собой). Алгоритм вычёркивания занимает полтора экрана, зато работает. Тест из трёх окружностей... Ооо, тру. Наконец-то. Так, попробуем посложнее... Блять. Ну что за жизнь-то. Мы не учли то, что если выкинуть из множества окружность, какие-то другие перестанут быть связанными. 12:30. А, чёрт с вами. Если умно всё написать, могут и не заподозрить что неправильно, таких как я полсотни, что, у всех что ли проверять? Пишем бюрократию, час дня, мама, я поехал, да, мама, опять не пожрал. Умру. Всё, пока.

13:45. На ФПМИ нас только трое. Остальные ушли поздравлять замдекана во второй корпус. А я опять оторвался от коллектива, как плохо. Препод начинает собираться уходить. Пацаны, давайте быстрее, еёщ быстрее. А, вот вы, пацаны. А можно РГЗ сдать? Как нет? Как нет? А, ну завтра на консультации, пол-одиннадцатого вечера, окей-окей. «Так, молодые люди, послушали все сюда внимательно! Завтра на консультацию приносим РГЗ. Приходим все со своими ноутбуками, чтобы показывать программы, терминалки будут заняты!» Да бля, давно хотел купить ноут, щас перед психологией сгоняю куплю. Ладно, дэвушки принесут. А вот показывать программу с поддельными результатами тестов — проблема. Может видео снять, как она работает лол? ГГ блять, приду домой и опять это решать.

20:30. С начала решения задачи прошло более 24 часов. Первый раз со мной такое. Так, ну не хотите интеллектуально, будем в лоб перебирать. Так, Sergey89 ICQ, ё, ниггер, слухай, как перебрать все неупорядоченные подмножества? О, код на PHP, спасибо. Сейчас перепишу на Си. Неоднородный массив, конкатенация целых чисел, спасибо, Серёжа! Google! Так, рекурсивный перебор, правительство РФ, курс дискретной математики в СпбГУ... Рекурсия. Десять вкладок в Kate, везде разные алгоритмы, некоторые даже работают, но до того страшные и непонятно как же их встраивать в мой исходник. 35 строчек правильных. Жесть. А, вот. Двоичный перебор. Не совсем понятно правда как это работает:

for (n = N; n > 1; n--)
    {
        for (m = quantity - 1; m > 0; m--)
        {
            int buffer[100], bufferLength = 0;
            for (l = 0; l < N; l++)
            {
                if (((m >> l) & 1) == 1)
                {
                    buffer[bufferLength++] = l;
                }
            }

Но работает. А язык математики поможет описать непонятное нам самим так, словно мы это понимаем. Исходник, тесты, заебись, работает, отчёт, родители спят, а принтер шумит на всю квартиру, 01:00, конец. Решил. Спать. А, нет. Ещё весёлый баг:

Размер шрифта всё увеличивается и увеличивается, и если крутануть чуть ниже, Opera повиснет. Ну это я из Wiki-разметки так автозаменой перевёл . Всё. А, ещё SMS старосте чтобы не отмечала. А то взяла моду. И матан решать надо будет утром.