时间戳

首页 > 解决方案 > 与平面上的点相关的问题和一些技术错误 [C++]

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

问题描述

问题陈述：给定平面上的 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;
}

标签： c++arraysalgorithmgeometry

解决方案

我认为你不需要蛮力它，至少n^2logn应该比 n^3 更好。我不会用 C++ 写出代码，但我会解释一下算法：

  1. 将每个点视为集线器的中心，通过线连接到所有其他点。然后具有该中心的每一对点与 x 轴形成一定的角度，您可以简单地使用 arctan(deltay/deltax) 来查找。

  2. 对于每个中心，您可以对角度进行排序 ( nlogn)，并且很容易知道O(1)该组角度的中值角度是多少，从而知道要添加到列表中的对。这是一个极端情况，可能有几个共线对，所以不要忘记这一点。

  3. 因此，如果您对 n 个点执行此操作，对 nlogn 次进行排序，您将得到解决方案n^2logn

推荐阅读