fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <functional>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. class QPointF
  8. {
  9. public:
  10.     QPointF(double xpos, double ypos) : xp(xpos), yp(ypos) {}
  11.  
  12.     inline bool operator==(const QPointF &p) {
  13.     	return p.x() == xp && p.y() == yp;
  14.     }
  15.  
  16.     double x() const { return xp; };
  17.     double y() const { return yp; };
  18.  
  19. private:
  20.     double xp;
  21.     double yp;
  22. };
  23.  
  24. class LessYComparator
  25. {
  26. public:
  27.  
  28.     inline bool operator() (const QPointF& p1, const QPointF& p2)
  29.     {
  30.         return (p1.y() < p2.y());
  31.     }
  32.  
  33.     bool cmp(const QPointF &p1, const QPointF &p2) {
  34.         return p1.y() < p2.y();
  35.     }
  36. };
  37.  
  38. class LessXComparator
  39. {
  40. public:
  41.  
  42.     inline bool operator() (const QPointF& p1, const QPointF& p2)
  43.     {
  44.         return (p1.x() < p2.x());
  45.     }
  46.  
  47.     bool cmp(const QPointF &p1, const QPointF &p2) {
  48.         return p1.x() < p2.x();
  49.     }
  50. };
  51.  
  52. void partitionField(std::vector<QPointF>* field,
  53.                     const int leftIndex,
  54.                     const int rightIndex,
  55.                     const std::function<int(QPointF)>& medianCompare)
  56.   {
  57.     auto leftIt = field->begin() + leftIndex;
  58.  
  59.     // Ende ist bei std::partition() explizit, deshalb + 1
  60.     auto rightIt = field->begin() + rightIndex + 1;
  61.  
  62.     std::stable_partition(leftIt, rightIt, medianCompare);
  63.   }
  64.  
  65. int main() {
  66. 	  std::vector<QPointF> xPoints = {
  67.     QPointF(-0.9123711701495426, 0.31958762886597936),
  68.     QPointF(0.5000000197994668, 0.19072164948453607),
  69.     QPointF(-0.5051546591788427, 0.7010309278350515),
  70.     QPointF(-0.18041237827815806, 0.6649484536082475),
  71.     QPointF(0.7938144644238956, 0.6907216494845361)
  72.   };
  73.  
  74.   std::vector<QPointF> yPoints = xPoints;
  75.  
  76.   std::sort(xPoints.begin(), xPoints.end(), LessXComparator());
  77.   std::sort(yPoints.begin(), yPoints.end(), LessYComparator());
  78.  
  79.   int leftIndex = 0;
  80.   int rightIndex = yPoints.size() - 1;
  81.   int medianIndex = (leftIndex + rightIndex + 1) / 2;
  82.  
  83.   QPointF yMedian = yPoints[medianIndex];
  84.  
  85.   const auto compare = [yMedian](const QPointF& point) {
  86.     return point.y() < yMedian.y();
  87.   };
  88.  
  89.   partitionField(&xPoints, leftIndex, rightIndex, compare);
  90.  
  91.   std::cout << "Median gefunden? : " << (xPoints[medianIndex] == yPoints[medianIndex]) << std::endl;
  92.  
  93. 	return 0;
  94. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Median gefunden? : 0
https://ideone.com/MZoeBL
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!