c++ - 订单 : An Analysis on Point Sorting

Question

所以我为自己制作了一个点打印类，应该让用户输入二元组；即 x 和 y，然后按 ^order,^ 将它们打印回给用户，其中 order 表示 p1=(x,y)

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

class Point2D {
public:
    Point2D();
    Point2D(double a, double b);

    double getx();
    double gety();

    void setx(double a);
    void sety(double b);

    virtual void print();
    virtual void print(int a);

    double angle();

private:
    double x;
    double y;
};

bool operator<( Point2D a , Point2D b );

int main() {

    double my_x=-999;
    double my_y=-999;
    string my_color;
    double my_weight;
    vector<Point2D*> points;

    cout << "Welcome to Point Printer! Please insert the x-and y-coordinates for your points and I will print them in sorted order! Just one rule, the point (0,0) is reserved as the terminating point, so when you are done enter (0,0).\n";

    while(true)
    {
        cout << "x = ";
        cin>>my_x;
        cout << "y = ";
        cin>>my_y;
        if((my_x == 0)&&(my_y==0))
        {
            break;
        }
        points.push_back(new Point2D(my_x, my_y));
    }
    sort(points.begin(), points.end());

    cout << "\n\n";
    cout << "Your points are\n\n";

    for(int i=0;i<points.size();i++)
    {
        cout<<i+1<<": ";
        (*points[i]).print(); cout<<endl; // this is the printing gadget
    }
    for(int i=0; i<points.size(); i++) 
    {
        delete points[i];
    }
    cout << endl << endl;

    return 0;

}

double Point2D::angle()
{
    double Angle = atan2(y,x);
    if(Angle < 0)
    {
        return Angle + 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;
    }
    return Angle;
}

bool operator< (Point2D a, Point2D b)
{
    if (a.getx()*a.getx()+a.gety()*a.gety() < b.getx()*b.getx()+b.gety()*b.gety())
    {
        return true;
    }
    else if (a.getx()*a.getx()+a.gety()*a.gety() > b.getx()*b.getx()+b.gety()*b.gety())
    {
        return false;
    }
    if (a.getx()*a.getx()+a.gety()*a.gety() ==b.getx()*b.getx()+b.gety()*b.gety())
    {
        if (a.angle() < b.angle())
        {
            return true;
        }
        else if (a.angle() > b.angle())
        {
            return false;
        }
    }
    return true;
}

Point2D::Point2D() { x = 0; y = 0; return;}

Point2D::Point2D(double a, double b) { x = a; y = b; return;}

double Point2D::getx() { return x;}
double Point2D::gety() { return y;}

void Point2D::setx(double a) { x = a; return; }
void Point2D::sety(double b) { y = b; return; }

void Point2D::print() {
    cout<<"("<<x<<","<<y<<")";
    return;
}

void Point2D::print(int a) {
    print(); cout<<endl;
}

我遇到的问题是以下任一情况:

sort

angle()

operator<(Point2D a, Point2D b)

Something different entirely...

特别是以下几点:

x = 1
y = 2
x = 2
y = 3
x = 1.1
y = 2.2
x = -10
y = 10
x = -5
y = -3
x = -5
y = 3
x = 5
y = -3
x = 5
y = 3
x = 0
y = 0

未按正确顺序排序。

任何帮助将不胜感激。谢谢。

Answer 1

问题(或其中之一)是比较函数中的最终语句。

return true;

看看这个 block :

if (a.getx()*a.getx()+a.gety()*a.gety() ==b.getx()*b.getx()+b.gety()*b.gety())
{
    if (a.angle() < b.angle())
    {
        return true;
    }
    else if (a.angle() > b.angle())
    {
        return false;
    }
}

首先，如果我们已经到了这一点，我们已经确定 (x*x + y*y)两者的计算 a和 b是平等的。现在让我们假设角度也相等。会发生什么？第一次测试失败，因为 a.angle()不小于b.angle() .然后第二次测试失败，因为 a.angle()不大于 b.angle() .然后你返回 true。换句话说，你是说 a 是真的小于 b ，尽管无论如何，它们应该被认为是相等的，所以你应该返回 false。您可以 return a.angle() < b.angle(); 而不是对角度进行多次测试，这应该可以解决问题。通过一些额外的简化，您的函数应如下所示:

bool operator<(Point2d a, Point2d b)
{
    double A = a.getx()*a.getx()+a.gety()*a.gety();
    double B = b.getx()*b.getx()+b.gety()*b.gety();

    if (A < B) return true;
    if (A > B) return false;
    return a.angle() < b.angle();
}