Это немного не то, но суть схожая

Попробуйте покурить диаграммы Вороного

Ща чекну, спс

Есть множество точек, нет повторяющихся. Из этих точек нужно выбрать все равнобедренные треугольники. Количество точек 1500 макс

а точки действительные координаты имеют? не целые?

Оффтоп

а точки действительные координаты имеют? не целые?

целые

Есть множество точек, нет повторяющихся. Из этих точек нужно выбрать все равнобедренные треугольники. Количество точек 1500 макс

Точки в эвклидовом пространстве?

Попробуйте покурить диаграммы Вороного

Триангуляция Делоне ему нужна

Или нужно вообще все возможные треугольники выбрать?

Ищем треугольники ABC, где AB = AC. Зафиксировали A (перебрали во внешнем цикле точку). Перебрали все остальные точки X, посчитали расстояния AX, отсортировали по нему или засунули в хеш-таблицу. Получили несколько групп точек с одинаковым расстоянием. Если в какой-то группе k точек, то это порождает k * (k - 1) / 2 треугольников — выбрать B и C из группы. Осталось вычесть крайние случаи: три точки на одной прямой (которые мы зря посчитали за треугольник) и равносторонние треугольники (которые мы посчитали три раза, а надо один), это оставляется читателю в качестве упражнения.

С чего это?

(0,0) (-2,-2) (2,-2)

равнобедренный треугольник

в чем нетрудно убедиться

Ноль равносторонних, а просят равнобедренные. (Зато это ответ на вторую половину оставленного мной упражнения.)

Про равносторонние я согласен

Мне нравится уверенность с которой рекомендуют диаграмму Вороного.

Мне нравится уверенность с которой рекомендуют диаграмму Вороного.

Диаграмма Вороного никогда не помешает! Например тут ее можно использовать вместо сортировки.

Ищем треугольники ABC, где AB = AC. Зафиксировали A (перебрали во внешнем цикле точку). Перебрали все остальные точки X, посчитали расстояния AX, отсортировали по нему или засунули в хеш-таблицу. Получили несколько групп точек с одинаковым расстоянием. Если в какой-то группе k точек, то это порождает k * (k - 1) / 2 треугольников — выбрать B и C из группы. Осталось вычесть крайние случаи: три точки на одной прямой (которые мы зря посчитали за треугольник) и равносторонние треугольники (которые мы посчитали три раза, а надо один), это оставляется читателю в качестве упражнения.

Не хватает квадродерева

Диаграмма Вороного никогда не помешает! Например тут ее можно использовать вместо сортировки.

Нет, нельзя, тебе нужны не только ближайшие в каком-либо смысле точки.

Нет, нельзя, тебе нужны не только ближайшие в каком-либо смысле точки.

В каком смысле? В вашем решении вы сортируете точки по расстоянию относительно фиксированной точки. То же самое можно сделать обходя треугольники в триангуляции. Асимптотика не улучшилась, зато диаграмма пригодилась!

Ах вот так! Ну ладно, ладно :)

Вообще я не знаю, насколько честно оставлять читателям упражнение "посчитайте число равносторонних треугольников с целыми координатами"

Я понял, спасибо огромное!

Я понял, спасибо огромное!

??? Это вопрос был

лобовое решение: для N точек имеем N*(N-1)/2 отрезков между ними. вычисляем их, сортируем, потом проверяем все равные на принадлежность общей вершине.

short int достаточно, это меньше 4.5 млн на отрезок.( индексы координат + длина)

ребят а в .cpp при определении объявленного в .h метода валидно писать decltype уот так уот: void MyClass::updateField(decltype(m_field) &&newValue) ?

Как угодно

что вместо его можно юзать?

Ну, например, можно просто использовать глобальную переменную, если не фанатствовать с этим

Да Синглтон вообще дурацкий паттерн. Это глобальная переменная закопанная в функцию, и все. Все его проблемы - это как его правильно создать, и решаются они очень просто, если все создать явно.

Вообще Синглтон зачем нужен? Он просто переводит зависимость функции от переменной в разряд зависимостей функции от функции.

Вообще Синглтон зачем нужен? Он просто переводит зависимость функции от переменной в разряд зависимостей функции от функции.

С учётом того, что найти функцию и переменную одинаково сложно, в общем, все напрасно. Т.е. конечно немного вызов функции чуть более грибок чем ссылку на переменную, но кардинально разницы мало.Может я сейчас конечно что-то забыл и упустил из виду, но по большому счету это так.

Создавать объект явно выше по логике, и передавать егокак зависимость, параметром в функции и конструкторы

Ну да, конечно, под час это минус один параметр....

Вообще Синглтон зачем нужен? Он просто переводит зависимость функции от переменной в разряд зависимостей функции от функции.

Еще ленивая потокобезопасная инициализация.

Dependency injection

Да бля запихай этот DI себе в зад вместе с Java... Его и в Java делают все, а нужно оно реально в 5-10% случаев...

Да бля запихай этот DI себе в зад вместе с Java... Его и в Java делают все, а нужно оно реально в 5-10% случаев...

Извини за нетолерантность...

Можно ли тип int (*fun1)(void *) приводить к int (*fun2)(void *, int, void*, void* ) ?

. Нет

Я просто читаю код libpcap и там такое интересное написано

. Расскажи нам....

Это ж undefined behavior наверняка, привет компилятору.

Не, это хуже...

Есть множество точек, нет повторяющихся. Из этих точек нужно выбрать все равнобедренные треугольники. Количество точек 1500 макс

А что тебя выручать, NP-complete task....

Как обход за 1 с можно сделать?

Возми очень хороший процессор....

это на плюсах 10^8 операций

А не на плюсах что, меньше операций или больше?

Не, это хуже...

Насколько?)

Ищем треугольники ABC, где AB = AC. Зафиксировали A (перебрали во внешнем цикле точку). Перебрали все остальные точки X, посчитали расстояния AX, отсортировали по нему или засунули в хеш-таблицу. Получили несколько групп точек с одинаковым расстоянием. Если в какой-то группе k точек, то это порождает k * (k - 1) / 2 треугольников — выбрать B и C из группы. Осталось вычесть крайние случаи: три точки на одной прямой (которые мы зря посчитали за треугольник) и равносторонние треугольники (которые мы посчитали три раза, а надо один), это оставляется читателю в качестве упражнения.

И чего, ты так из NP полноты убежишь?

Насколько?)

Намного

Мне нравится уверенность с которой рекомендуют диаграмму Вороного.

+1

А конкретнее можно?))

Диаграмма Вороного никогда не помешает! Например тут ее можно использовать вместо сортировки.

Вместо сортировки чего?

Вместо сортировки чего?

Расстояний от фиксированной точки до всех остальных. Это сообщение было сарказм, можно расслабиться :)

Есть множество точек, нет повторяющихся. Из этих точек нужно выбрать все равнобедренные треугольники. Количество точек 1500 макс

Точек 1500. Значит расстояний всего 2.2*10^6. Кладём все отрезки в массив, сортируем, выбираем одинаковые. Всё, конец истории, решается за квадрат * лог

А конкретнее можно?))

Блин,UB это UB. Это значит по русски "хрен знает" или "хер проссыт" , но это не безнадежно! Это не обязательно, что не будет работать! Это неизвестность. А вот вызов функции с тремя параметрами с указанием только одного параметра - это гарантированная, 200% ная жопа.

Точек 1500. Значит расстояний всего 2.2*10^6. Кладём все отрезки в массив, сортируем, выбираем одинаковые. Всё, конец истории, решается за квадрат * лог

Нихрена

Мне казалось человек наоборот хочет, передать однопараметровую в качестве трех

1500*1500=2.250.000 отрезков

Точек 1500. Значит расстояний всего 2.2*10^6. Кладём все отрезки в массив, сортируем, выбираем одинаковые. Всё, конец истории, решается за квадрат * лог

хватит оффтопить. идите в алгоритмы и там решайте

Мне казалось человек наоборот хочет, передать однопараметровую в качестве трех

Да пофигу, то же самое

template <typename T> struct Base { using Item = typename T::Item; }; struct X {}; struct Derived: Base<Derived> { using Item = X; }; Такое не компилируется, как обходить?

Очень много хочешь)

Модно в шаблон добавить параметр чему равен Item

С дефолтным

Модно в шаблон добавить параметр чему равен Item

Собственно сейчас оно так и есть. Проблема в том что в Base нужно пробрасывать не один тип, а несколько, что весьма неудобно.

Вроде сторонним трейтом должно быть можно.

Хм, вроде вариант.

. Расскажи нам....

Там кастинг указателей на функции

А что тебя выручать, NP-complete task....

Откуда там NP?

Точки в эвклидовом пространстве

Делаем R-tree

Строим сетку Делоне

Аааа

Я забыл, что вам нужны любые треугольники

Да пусть даже и так.

Да нет там NP никак, задача сверху оценивается как N^3, решение уже предложили на N^2

Да нет там NP никак, задача сверху оценивается как N^3, решение уже предложили на N^2

Вот и мне кажется

Да нет там NP никак, задача сверху оценивается как N^3, решение уже предложили на N^2

N^2 log N так-то :)

N^2 log N так-то :)

Смотря какое решение. С сортировками — да.

Тут надо догадаться какие индексы построить

Вообще задачу можно записать в виде SQL запроса

И отсюда станет понятно мне кажется

Да бля запихай этот DI себе в зад вместе с Java... Его и в Java делают все, а нужно оно реально в 5-10% случаев...

Итить вы тут дружелюбные.

Итить вы тут дружелюбные.

Это ещё не бомбит

Налицо детская травма. Но вот почему? Чем DI жизнь то испортил? (Как идея, а не пример где кто-то не умеет готовить)

Да бля запихай этот DI себе в зад вместе с Java... Его и в Java делают все, а нужно оно реально в 5-10% случаев...

Я в плюсах использую для тестового окружения

Ищем треугольники ABC, где AB = AC. Зафиксировали A (перебрали во внешнем цикле точку). Перебрали все остальные точки X, посчитали расстояния AX, отсортировали по нему или засунули в хеш-таблицу. Получили несколько групп точек с одинаковым расстоянием. Если в какой-то группе k точек, то это порождает k * (k - 1) / 2 треугольников — выбрать B и C из группы. Осталось вычесть крайние случаи: три точки на одной прямой (которые мы зря посчитали за треугольник) и равносторонние треугольники (которые мы посчитали три раза, а надо один), это оставляется читателю в качестве упражнения.

О, это ж тасочка с ACMP.

N^2 log N так-то :)

Я согласен полностью. Не знаю где там Илья нашёл NP. Но есть у него привычка, кое какая.

Что тут происходит вообще?

Я согласен полностью. Не знаю где там Илья нашёл NP. Но есть у него привычка, кое какая.

Ну, докажите, что не NP, ok...

@burunduk3 привел выше конструктивное решение

Все уже, не катит...я сплю