在平面内有一些点 找出一个算法来算出一条给定斜率的直线把这些点分成数量相等的两堆,该如何处理

在平面内有一些点 找出一个算法来算出一条给定斜率的直线把这些点分成数量相等的两堆
在平面内有一些点 找出一个算法来算出一条给定斜率的直线把这些点分成数量相等的两堆
点落在线上可以算作任意一堆的~~

后面给了HINT。。。 To solve this problem reduce it to the problem of finding a median in a set of numbers.

依然不知从何下手。。。求助大神。。

------解决方案--------------------
你可以任意给个起点，把直线确定下来，然后计算每个点到直线的距离，距离要带符号，在直线上方的为正，下方的为负
这样每个点都对应了一个浮点数，找这些数的中位数，让直线过这个数对应的点就ok了
------解决方案--------------------
中位数可以做到O(n)
顶michael122
实数的排序算法复杂度是O(nlogn)，这个中位数可以做到O(n)


下面我来说明这个算法的过程。
算法是基于归并排序（merge-sort）的更改。
把中位数更改为等价的叙述。无序的n个数中的第int(n/2)大的元素。(k=int(n/2))

1.随机化数据，这样可以保证因为输出时候的对称性（可能的顺序输入）而造成的算法退化。
for (int i=number.count;i>=0;i--)
swap(number[i],number[random(0,i-1)]);//swap，交换，random，0，k闭区间的随机数。
2.归并排序主过程。
mergesort(a,b,k)//寻找number数组中从下标a到下标b的元素中的第k大的元素。
{
t=number[a];
把这a,b中的元素从排，使a~p-1的元素比t小，p+1~b的元素比t大。number[p]=t;//O(n)，这步你构造吧。不是很困难，伪代码不写太多。
//此时比t小元素有p-1-a+1=p-a个,
//分情况，如果k=p-a+1,返回t
//如果k>p-a+1,返回mergesort(p+1,b,k-(p-a+1))
//如果k<p-a+1,返回mergesort(a,p-1,k)
}

以上算法T(n)=T(n/2)+O(n)
根据主定理，T(n)=O(n)。

------解决方案--------------------

探讨

你可以任意给个起点，把直线确定下来，然后计算每个点到直线的距离，距离要带符号，在直线上方的为正，下方的为负
这样每个点都对应了一个浮点数，找这些数的中位数，让直线过这个数对应的点就ok了