与平面上的点有关的问题和一些技术错误[C++]

Question

问题陈述：给定平面上的n个点（n为偶数）。找出使穿过它们的直线两侧的点数相等的点对的数量。

我正在尝试暴力破解 (~O(n^3))，非常感谢任何关于改进解决方案的建议。我也发现了这个同样的问题，但无法实现它。

主要技术问题：我已经将导致错误的部分标记为// HERE。更准确地说，错误是：

error: no matching function for call to 'sign'
                if(sign(A, B, M) == 1) right++;

error: no matching function for call to 'sign'
                if(sign(A, B, M) == -1) left++;

我认为我在定义 A、B 和 C 时可能犯了 & 的错误。我该如何解决？

我的代码：

#include <iostream>
using namespace std;

// check which side of the line AB does the point M lie on
int sign(float A[2], float B[2], float M[2]) {
  float det = (A[0] - M[0]) * (B[1] - M[1]) - (B[0] - M[0]) * (A[1] - M[1]);
  if(det > 0) return 1;
  if(det < 0) return -1;
  else return 0;
}

int main() {
    int n, res = 0;
    cin >> n;
    float points[n][2]; // array of points

    // enter points via coordiantes
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 2; j++) {
        cin >> points[i][j];
        }      
    }
    
    // brute force :(
    for(int i = 0; i < n; i++) {
        int left = 0, right = 0;
        float &A = *points[i];
        for(int j = 0; i < n; i++) {
            if(j == i) continue;
            float &B = *points[j];
            for(int k = 0; k < n; k++) {
                if(k == j || k == i) continue;
                float &M = *points[k];
                if(sign(A, B, M) == 1) right++; // HERE
                if(sign(A, B, M) == -1) left++; // HERE
            }
        }
        if(left == right) res++;
    }
  cout << res << endl;
  return 0;
}

Answer 1

我觉得不用暴力破解，至少n^2logn应该比n^3好。我不会用 C++ 写出代码，但我会解释算法：

将每个点想象成一个枢纽的中心，通过线连接到所有其他点。然后每对以该中心为中心的点与 x-axis 成一定角度，您可以简单地使用 arctan(deltay/deltax) 来找到。
对于每个中心，您可以对角度进行排序（nlogn），并且在O(1)中很容易知道那组角度的中间角度是多少, 因此要添加到列表中的对。这是一个极端情况，可能有几个 co-linear 对，所以不要忘记这一点。
所以如果你对 n 个点这样做，排序 nlogn 次，你会在 n^2logn
中得到解决方案

与平面上的点有关的问题和一些技术错误[C++]

Problem related to points on a plane and some technical errors [C++]

c++

arrays

algorithm

geometry