is_symmetrical.cpp

#include <cassert>
#include <unordered_set>
#include <vector>

// 21:30 - 22:16

struct TPoint {
    double X;
    double Y;
};
bool operator<(const TPoint &First, const TPoint &Second) {
    return First.X < Second.X;
}
bool operator>(const TPoint &First, const TPoint &Second) {
    return First.X > Second.X;
}
bool operator==(const TPoint &First, const TPoint &Second) {
    return First.X == Second.X && First.Y == Second.Y;
}
namespace std {
    template <>
    struct hash<TPoint> {
        std::size_t operator()(const TPoint &k) const {
            return hash<double>()(k.X) + hash<double>()(k.Y);
        }
    };
}
using TPoints = std::vector<TPoint>;

TPoint FindNth(const TPoints::iterator Begin, const TPoints::iterator End, size_t ToFind) {
    const TPoints::iterator &Pivot   = std::next(Begin, (End - Begin) / 2);
    TPoints::iterator        LeftIt  = Begin;
    TPoints::iterator        RightIt = End - 1;
    for(; LeftIt != RightIt;) {
        for(; *LeftIt < *Pivot && LeftIt <= Pivot; ++LeftIt) // Find first not in order on the left
            ;
        for(; *RightIt > *Pivot && RightIt >= Pivot; ++RightIt) // Find first not in order on the right
            ;
        std::swap(*LeftIt, *RightIt);
    }
    const size_t SizeOfLeftPart = LeftIt - Begin;
    TPoint       Result;
    if(SizeOfLeftPart == ToFind)
        Result = *LeftIt;
    if(SizeOfLeftPart >= ToFind)
        Result = FindNth(Begin, LeftIt, ToFind);
    else
        Result = FindNth(LeftIt, End, ToFind - SizeOfLeftPart);
    return Result;
}

double FindMedian(TPoints Points) {
    if(Points.size() % 2 == 0) {
        const TPoint &First  = FindNth(Points.begin(), Points.end(), Points.size() / 2);
        const TPoint &Second = FindNth(Points.begin(), Points.end(), Points.size() / 2 + 1);
        return (First.X + Second.X) / 2.;
    } else {
        const TPoint &Result = FindNth(Points.begin(), Points.end(), Points.size() / 2);
        return Result.X;
    }
}

bool IsSymmetrical(const TPoints &Points) {
    std::unordered_set<TPoint> Hash;
    for(const TPoint &Point : Points)
        Hash.insert(Point);
    const double X = FindMedian(Points);
    for(const TPoint &Point : Points) {
        if(Point.X >= X)
            continue;
        const TPoint Mirrored = {Point.X + 2. * (X - Point.X), Point.Y};
        if(Hash.find(Mirrored) == Hash.end())
            return false;
    }
    return true;
}

// ================================================================================================================

// void Check(TImpl &&Impl, const std::string &First, const std::string &Second, size_t Expected) {
//     const size_t Actual = Impl(First, Second);
//     if(Actual != Expected) {
//         std::cout << "Actual: " << Actual << ", Expected: " << Expected << std::endl;
//     }
// }

int main() {

    return 0;
}