Помогите решить задачу по c++!

Question

Помогите решить задачу по c++!

Серёжа Завьялов Ученик (100), на голосовании 3 недели назад

Напишите структуру:
struct Circle {
int x, y, r;
char color;
Circle(int x, int y, int r, char color);
}
У нее 4 поля, x - x-координата, y - y-координата, r - радиус круга, color - цвет круга.
Также реализуйте конструктор, как написано выше.
В этой задаче мы считаем, что два круга равны, если у них совпадают обе координаты, а также радиус. Круги могут быть двух разных цветов, но если всё остальное совпадает, эти круги считаются равными
Задача не была бы настолько простой, если бы не следующее:
Подружите эту структуру с std::unordered_set. Иными словами, необходимо написать такой код, который позволил бы использовать структуру Circle вместе с std::unordered_set, не указывая никакие дополнительные шаблонные параметры, кроме самого Circle.
Пример теста:
std::unordered_set<Circle> st;
Circle blue1(5, 6, 7, 'b');
Circle red1(5, 6, 7, 'r');
Circle blue2(6, 5, 7, 'b');
Circle red2(1, 1, 1, 'r');
st.insert(blue1);
assert(st.size() == 1);
st.insert(blue2);
assert(st.size() == 2);
st.insert(red1);
assert(st.size() == 2);
st.insert(red2);
assert(st.size() == 3);
В систему отправляйте лишь код самой структуры, а также дополнительный код, если он потребуется. Весь этот код будет включен перед тестами.

Answer 1

Dmitry Просветленный (22415) 1 месяц назад

 #include 

struct Circle {
    int x, y, r;
    char color;
    Circle(int x, int y, int r, char color) : x(x), y(y), r(r), color(color) {}
};

bool operator==(const Circle& lhs, const Circle& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y && lhs.r == rhs.r;
}

template <>
struct std::hash {
    std::size_t operator()(const Circle& c) const noexcept {
        return c.x ^ (c.y << 1) ^ (c.r << 2);
    }
};

Серёжа ЗавьяловУченик (100) 1 месяц назад

спасибо! программа компилируется, но проверяющий компилятор выдает time-limit-error, можете пожалуйста убыстрить код?

Dmitry Просветленный (22415) Серёжа Завьялов, потому что я написал банальную хеш-функцию ради примера. Попробуйте тогда на FNV-1a хеш заменить:

 template <>
struct std::hash {
	std::size_t operator()(const Circle& c) const noexcept {
		const char* begin = reinterpret_cast(&c);
		const char* end = begin + sizeof(c.x) + sizeof(c.y) + sizeof(c.r);
		constexpr std::size_t offsetBasis = sizeof(std::size_t) == 4 ? 2166136261 : 14695981039346656037;
		constexpr std::size_t fnvPrime = sizeof(std::size_t) == 4 ? 16777619 : 1099511628211;
		std::size_t h = offsetBasis;
		for (; begin < end; ++begin)
			h = (h ^ (*begin)) * fnvPrime;
		return h;
	}
};