Как оптимизировать данный код?

Question

[Di_Brain]

Вот сам код:

#include <iostream>
using namespace std;
 
 
int main() {
    long long x, y, s = 0, max = 0, i1 = 0;
    int r;
    cin >> r;
    for (int i = 1; i <= r; ++i) {
        s = 0;
        for (x = -i - 1; x <= i; ++x)
            for (y = -i - 1; y <= i; ++y)
                if (x*x + y * y == i * i) ++s;
        if (max < s) { max = s;  i1 = i; }
    }
    cout << i1;
    return 0;
}

При попытке сдать задачу выдает TL, можно ли как-то ускорить код, заменить циклы for или сократить их количество?

Comments

[Евгений Шатунов]

Ускорить-то, конечно, можно. Только без условия задачи - никак.

[Евгений Шатунов]

Di_Brain, ты уж извини, я с картинок не читаю. Мне свои глаза дороги.

[kirill_drashiga]

Я решил эту задачу частично. На 75 баллов с помощью генерации пифагоровых троек. Можем списаться в телеграмме например. Если ты уже решил эту задачу, то мне было бы интересно услышать решение, потому что алгоритм Брезенхэма работает еще медленее чем генерация троек. Мой тг: @DoniR112

Answer 1

[15432]

Можно отсечь почти все отрицательные х и у, можно вообще убрать перебор по i, можно наполовину сократить перебор по у

какой из вариантов вам кажется интереснее?
(имхо, достаточно будет избавиться от перебора по i)
и опубликуйте условие на всякий случай

Comments

[15432]

Di_Brain, делаете std::map, проходитесь по всем x и y, вычисляете r = √(x^2 + y^2), если число целое - увеличиваете счётчик в map[r]
потом из всех map[r] выбираете r с наибольшим счётчиком

для ещё большего ускорения можно воспользоваться симметрией круга и считать только x и y в пределах x = [0..n], y = [0..x], но там нужно правильно граничные случаи обрабатывать

[mayton2019]

Данная задача решается в целых числах с помощью алгоритма Брезенхема для окружности. А точнее для ее восьмой части. А чтобы получить всю площадь целых точек, то нужно брезенхем применить несколько раз для средней части круга (как мясная часть бургера) и для двух боковушек (хлеб). И сложить все.

[Евгений Шатунов]

mayton2019, а чего бы не выписать это как ответ?

[Di_Brain]

15432, только начал изучать stl, сейчас попытался сам все это перебрать и ничего не получается, могли бы помочь с кодом? Вопрос конечно глупый, но уже больше 2 часов пытаюсь решить настолько простую задачу и никакой результат...

[15432]

Di_Brain, ну попробуйте так, но чую, тоже не пройдёт по времени, если 100 000 000 подадут на вход. Там что-то про Брезенхема упоминали.

#include <iostream>
#include <map>
#include <cmath>
using namespace std;

int main() {
	count << n;
	map<int,int> counters;
	for (int x = 1; x < n; ++x)
		for (int y = 1; y < x; ++y)
		{
			long long s = (long long)x * x + (long long)y * y;
			long long r = sqrt(s);
			if (r*r == s)
			{
				counters[r] += 1;
			}
		}
	int maxCount = 0, maxR = 0;
	for (map<int,int>::iterator it=counters.begin(); it!=counters.end(); ++it)
	{
		if (it->second > maxCount)
		{
			maxCount = it->second;
			maxR = it->first;
		}
	}
    cout << maxR;
	return 0;
}