在2D平面中分割一组点 [英] Partitioning a set of points in 2D plane

问题描述

问题陈述是-为您提供了一组N点，其中N为偶数，N <=1000.必须找到点对的数量，这样，如果您在那对点之间画一条线，则该线的每一侧都将包含相等的点数(N/2-1)."我不知道如何在O(n ^ 2)或更短的时间内解决这个问题?这是我的暴力解决方案-

The problem statement is - "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)." I can't figure out, how to solve this problem in O(n^2) or less time? Here is my brute-force solution-

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;
}

有什么方法可以优化解决方案?

Is there any way to optimize the solution?

推荐答案

有一种简单的方法可以在O(n ^ 2 log n)时间执行此操作.

There's a simple way do do this in O(n^2 log n) time.

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)时间才能完全排序)，但是我无法证明这一点此刻.

Perhaps the sorting time could be cut down because a sorted array of slopes would become nearly sorted (only requiring O(n) time to fully sort) when transforming polar co-ordinates to another origin, but I can't prove this at the moment.

这篇关于在2D平面中分割一组点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！