c++ - 共线点 C++

Question

我有一个脚本要求您输入一个数字n，然后要求您输入n 个(x,y) 点。

最后，脚本根据 x

对 (x,y) 点进行排序

我需要的是检测共线点并删除它们，这样脚本将只有一般位置的点。

例如:

输入

10
8   16
2   16
5   9
9   16
15  18
3   17
8   10
3   12
10  17
5   17

输出

2 16
3 12
5 9
5 17
8 10
9 16
10 17
15 18

我的脚本是这样的:

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int n,m;
class punto{
private:
    int x;
    int y;
public:
    punto();
    ~punto(){}
    void setx(int xn){ x = xn;}
    void sety(int yn) { y = yn; }
    void printcoord();

    friend bool compare_x(const punto& lhs, const punto& rhs);
    friend bool compare_y(const punto& lhs, const punto& rhs);
    };
punto::punto()
{
    x=0;
    y=0;
}
void punto:: printcoord()
{
    cout << x << " " << y << endl;
}
bool compare_x(const punto& lhs, const punto& rhs) {
    if (lhs.x == rhs.x)
        return lhs.y < rhs.y;
    return lhs.x < rhs.x;
}

int main()
{
    vector<punto> list;
            int x;
        int y;
        punto *p1;
    cin >>n;
    for(int contador=0; contador<n; contador++){
        if(contador<n){
                cin >> x;
                cin >> y;
                p1=new punto;
                p1->setx(x);
                p1->sety(y);
                list.push_back(*p1);
                cin.get();
            }
        }
    vector<punto>::iterator it;
     std::sort(list.begin(), list.end(), compare_x);
     for ( it = list.begin(); it != list.end(); ++it ) {
            it->printcoord();
     }
    return 0;
}

如您所见，我缺少确定共线点并将其删除的函数。

如果有任何帮助，我将不胜感激!

Answer 1

使用点积。令 a、b、c 为三个点。如果所有三个点都位于同一条直线上，则 vector b-a 和 vector c-a 的点积将为 |b-a||c-a|。

这是因为 cos(angle(bac))=dot(b-a,c-a)/(mag(b-a)*mag(c-a))。如果它们共线，则角度为零。零的余弦为一，所以 点(b-a,c-a)==mag(b-a)*mag(c-a)表示它们共线。

如果您的线性代数技能生疏或不存在，那么这里是复习

dot(w,v) = w.x*v.x + w.y*v.y
mag(v)=sqrt(v.x*v.x + v.y*v.y)

诀窍是以某种方式删除代价高昂的平方根函数。对两边求平方，你有

mag^2(v)=v.x*v.x+v.y*v.y 
cos^2(0)=1^2=1
dot^2(w,v)=(w.x*v.x + w.y*v.y)*(w.x*v.x + w.y*v.y)

检查一下

if( (v.x*v.x + v.y*v.y)*(w.x*w.x + w.y*w.y)) == (w.x*v.x + w.y*v.y)*(w.x*v.x + w.y*v.y) )