#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class QPointF
{
public:
    QPointF(double xpos, double ypos) : xp(xpos), yp(ypos) {}
    
    inline bool operator==(const QPointF &p) {
    	return p.x() == xp && p.y() == yp;
    }

    double x() const { return xp; };
    double y() const { return yp; };

private:
    double xp;
    double yp;
};

class LessYComparator
{
public:

    inline bool operator() (const QPointF& p1, const QPointF& p2)
    {
        return (p1.y() < p2.y());
    }

    bool cmp(const QPointF &p1, const QPointF &p2) {
        return p1.y() < p2.y();
    }
};

class LessXComparator
{
public:

    inline bool operator() (const QPointF& p1, const QPointF& p2)
    {
        return (p1.x() < p2.x());
    }

    bool cmp(const QPointF &p1, const QPointF &p2) {
        return p1.x() < p2.x();
    }
};

void partitionField(std::vector<QPointF>* field,
                    const int leftIndex,
                    const int rightIndex,
                    const std::function<int(QPointF)>& medianCompare)
  {
    auto leftIt = field->begin() + leftIndex;

    // Ende ist bei std::partition() explizit, deshalb + 1
    auto rightIt = field->begin() + rightIndex + 1;

    std::stable_partition(leftIt, rightIt, medianCompare);
  }

int main() {
	  std::vector<QPointF> xPoints = {
    QPointF(-0.9123711701495426, 0.31958762886597936),
    QPointF(0.5000000197994668, 0.19072164948453607),
    QPointF(-0.5051546591788427, 0.7010309278350515),
    QPointF(-0.18041237827815806, 0.6649484536082475),
    QPointF(0.7938144644238956, 0.6907216494845361)
  };

  std::vector<QPointF> yPoints = xPoints;

  std::sort(xPoints.begin(), xPoints.end(), LessXComparator());
  std::sort(yPoints.begin(), yPoints.end(), LessYComparator());

  int leftIndex = 0;
  int rightIndex = yPoints.size() - 1;
  int medianIndex = (leftIndex + rightIndex + 1) / 2;

  QPointF yMedian = yPoints[medianIndex];

  const auto compare = [yMedian](const QPointF& point) {
    return point.y() < yMedian.y();
  };

  partitionField(&xPoints, leftIndex, rightIndex, compare);
  
  std::cout << "Median gefunden? : " << (xPoints[medianIndex] == yPoints[medianIndex]) << std::endl;

	return 0;
}