e*****e
发帖数: 1275 | 1 Given a 2 dimensional plane in which there are n points. Give an algorithm
to generate the equation of a line that divides the plane such that there
are n/2 points on one side and n/2 points on the other. | j*****u
发帖数: 1133 | 2 按x或者y轴切可不可以？
找x或者y的median的两个点O(n)，然后中间随便画条线？
【在 e*****e 的大作中提到】
: Given a 2 dimensional plane in which there are n points. Give an algorithm
: to generate the equation of a line that divides the plane such that there
: are n/2 points on one side and n/2 points on the other.
| e*****e
发帖数: 1275 | 3 (1,1), (2,2), (3,3), (4,4)
x,y 的 median 会通过所有的点。。。。。而不是在线的两边 | n********y
发帖数: 66 | 4 how about these 2 lines ?
line1: x = 2.5
line2: y = 2.5 | j*****u
发帖数: 1133 | 5 不是啊，(2,2)和(3,3)之间平行于坐标轴的都可以
但是如果超过一半的点都平行于x或y轴，就不能平行于这个轴的线切了，要用另一个轴
做一下preprocess，还是O(n)
【在 e*****e 的大作中提到】
: (1,1), (2,2), (3,3), (4,4)
: x,y 的 median 会通过所有的点。。。。。而不是在线的两边
| a***i
发帖数: 39 | 6 i think he/she meant the lines x=2.5 or y=2.5 in this case.
【在 e*****e 的大作中提到】
: (1,1), (2,2), (3,3), (4,4)
: x,y 的 median 会通过所有的点。。。。。而不是在线的两边
| x*****p
发帖数: 1707 | 7 First, select a point O which is on the left of all n points. This point O
is the origin. For the other n points, sort them by the angle with respect
to O. If n is even, then get the middle two points, say A and B, select a
line with angle (A+B)/2 starting at O; if n is odd, then connect O with the
middle point. | p********u
发帖数: 86 | 8 跟你想的一样，但是3楼给出了反例
the
【在 x*****p 的大作中提到】
: First, select a point O which is on the left of all n points. This point O
: is the origin. For the other n points, sort them by the angle with respect
: to O. If n is even, then get the middle two points, say A and B, select a
: line with angle (A+B)/2 starting at O; if n is odd, then connect O with the
: middle point.
| c******w
发帖数: 1108 | 9 (1,1) (1,2) (1,3)
(2,1) (2,3)
(3,1) (3,2) (3,3)
这样的用平行于x或y轴的任何直线都无法切 | z****o
发帖数: 78 | 10 能不能这样, 按照x坐标排序, 最中间的两个记为 p1, p2, 如果 p1.x != p2.x 的话,
就用 x = 0.5*(p1.x+p2.x)来切开. 如果 p1.x == p2.x 的话, 统计在 x = p1.x 上面
的点. 假设有m个点q[1]~q[m]共线在 x = p1.x 上, 另外的点中, m1个点在左边, m2个
点在右边. q[1]~q[m] 按照 y 坐标从大到小排好序.
令O点是 q[n/2-m1] 和 q[n/2-m1+1] 的中点, 以O为轴顺时针转一个很小的角度arctan
(a). 得到的直线就是结果.
这个a的求法是: 对所有在O左下方的点W, a_left =max{ (O.y-W.y)/(O.x-W.x) } 即最
大斜率; 对所有在O右上的点W, a_right = max{ (W.y-O.y)/(W.x-O.x) } 也即最大斜
率; a = max{ a_left, a_right } *1.1
这样对不对? |
|
