MiddleКодИногдаЕщё не отвечали
Найти вертикальную ось симметрии множества 2D-точек за O(n)
Даны целочисленные точки на плоскости. Найдите x-значение вертикальной прямой, относительно которой всё множество симметрично, или сообщите, что такой нет.
Требования:
- Ось может быть нецелой; возвращайте
2*x(удвоенную), чтобы остаться в целых. - Цель — O(n) по времени.
// возвращает удвоенный x оси или std::nullopt, если вертикальной симметрии нет
std::optional<long long> symmetryAxis(const std::vector<std::pair<int,int>>& pts) {
// ваш код здесь
}Допишите реализацию.
Единственный кандидат на ось — (minX + maxX) / 2, поэтому удвоенная ось это minX + maxX. Кладём каждую точку в хеш-множество; для (x, y) зеркало — (minX + maxX - x, y). Если каждое зеркало есть, ось верна. Берём удвоенное значение, чтобы избежать дробей. O(n).
- ✗Сравнивать вещественные оси через float вместо удвоения для целочисленности
- ✗Считать осью центроид при неравномерном распределении
- ✗Переполнять
minX + maxXдля больших координат
- →Почему
minX + maxX— единственная возможная удвоенная ось? - →Как дублирующиеся точки влияют на проверку зеркал?
Оглавление
Задача
Найдите вертикальную ось симметрии целочисленных точек за O(n) или сообщите об отсутствии.
Решение
#include <vector>
#include <optional>
#include <unordered_set>
#include <climits>
std::optional<long long> symmetryAxis(const std::vector<std::pair<int,int>>& pts) {
if (pts.empty()) return std::nullopt;
long long minX = LLONG_MAX, maxX = LLONG_MIN;
auto key = [](long long x, int y){ return (x << 20) ^ (unsigned)y; };
std::unordered_set<long long> present;
for (auto& [x, y] : pts) {
minX = std::min(minX, (long long)x);
maxX = std::max(maxX, (long long)x);
present.insert(key(x, y));
}
long long doubledAxis = minX + maxX; // 2 * ось, целое
for (auto& [x, y] : pts)
if (!present.count(key(doubledAxis - x, y))) // зеркало присутствует?
return std::nullopt;
return doubledAxis;
}Ключевые моменты
- Единственный кандидат оси —
(minX + maxX) / 2; храним удвоенное целое. - Зеркало точки
(x, y)это(minX + maxX - x, y)— ищем в хеш-множестве. - Удвоение избегает float; следим за переполнением координат.
Оглавление
