在 2D 平面中划分一组点

Question

问题陈述是—— "You are given a set of N points, where N is even and N <= 1000. You have to find the number of pairs of points, such that if you draw a line through that pair, each side of the line will contains equal number of points(N/2-1)." 我想不通，如何在 O(n^2) 或更短的时间内解决这个问题？这是我的蛮力解决方案-

class Point{
public:
   int x, y;
   Point(){x = y = 0;}
   void make_point(int X, int Y){ x = X; y = Y; }
   int Point:: orientation (Point &p0, Point &p1){
     Point p2 = *this;
     Point a = p1 - p0;
     Point b = p2 - p0;
     int area = (a.x * b.y) - (b.x * a.y);
     if (area > 0)return 1;
     if (area < 0)return -1;
     return 0;
   }
};
int main() {
  Point p[4];
  p[0].make_point(0, 0);
  p[1].make_point(0, 1);
  p[2].make_point(1, 1);
  p[3].make_point(1, 0);
  int sz = sizeof(p) / sizeof(p[0]);
  int ans = 0;
  for (int i = 0; i < sz; i++){
    for (int j = i+1; j < sz; j++){
        int leftCnt = 0, rightCnt = 0;
        for (int k = 0; k < sz; k++){
            if (k == i || k == j)continue;
            if (p[k].orientation(p[i], p[j]) == 1)leftCnt++;
            if (p[k].orientation(p[i], p[j]) == -1)rightCnt++;
        }
        if (leftCnt == rightCnt && leftCnt == (sz/2-1))ans++;
    }
  }
  cout << ans << '\n';

  return 0;
}

有什么优化方案吗？

Answer 1

有一种简单的方法可以在 O(n^2 log n) 时间内完成。

for each point O in the set
   for each point A /= O
      calculate the slope of the ray OA 
   sort the points by the slope (this is the n log n limiting step) 
   for each point A /= O
      determine how many points are at either side of the line OA (this is an O(1) job)

也许可以减少排序时间，因为在将极坐标转换为另一个原点时，已排序的斜率数组将变得接近排序（只需要 O(n) 时间即可完全排序），但我不能现在证明这一点。

在 2D 平面中划分一组点

Partitioning a set of points in 2D plane

algorithm

partitioning

computational-geometry