MiddleCodeOccasionalNot answered yet
Find the vertical axis of symmetry of a set of 2D points in O(n)
Given integer points on a plane, find the x-value of a vertical line about which the whole set is symmetric, or report that none exists.
Requirements:
- The axis may be non-integer; return
2*x(doubled) to stay in integers. - Target O(n) time.
// returns the doubled axis x, or std::nullopt if no vertical symmetry exists
std::optional<long long> symmetryAxis(const std::vector<std::pair<int,int>>& pts) {
// your code here
}Write the implementation.
The only candidate axis is (minX + maxX) / 2, so the doubled axis is minX + maxX. Put every point in a hash set; for each point (x, y) its mirror is (minX + maxX - x, y). If every mirror is present the axis is valid. Use the doubled value to avoid fractions. O(n).
- ✗Comparing real-valued axes with floats instead of doubling to stay integer
- ✗Assuming the centroid is the axis when the distribution is uneven
- ✗Overflowing on
minX + maxXfor large coordinates
- →Why is
minX + maxXthe only possible doubled axis? - →How do duplicate points affect the mirror check?
Contents
Task
Find the vertical axis of symmetry of integer points in O(n), or report none.
Solution
#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 * axis, integer
for (auto& [x, y] : pts)
if (!present.count(key(doubledAxis - x, y))) // is the mirror present?
return std::nullopt;
return doubledAxis;
}Key points
- The only candidate axis is
(minX + maxX) / 2; keep the doubled integer. - The mirror of
(x, y)is(minX + maxX - x, y)— look it up in the hash set. - Doubling avoids floats; watch coordinate overflow.
Contents
