f****4
发帖数: 1359 | 1 Within a 2D space, there is a batch of points(no duplicate) in the region (0
,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2
parts with half points in each .the input will be an array of points and the
length of the array.
struct point{
int x;
int y;
};
input : struct point * points, int length
google了一下，说是Linear Perceptron algorithm可以解决，但找到的Linear
Perceptron 都是关于AI的；知道的人能给我个具体链接么？谢谢
算法压根就没准备那么深，临时抱佛脚中 |
x******3
发帖数: 245 | 2 看看这样行不
把所有点按照x或者y坐标排序，比如说按照x坐标排序， 然后找到x坐标的median， 划
条垂直线 |
a***g
发帖数: 234 | 3 这个不就直接bisection么
没有其他条件么
(0
the
【在 f****4 的大作中提到】
: Within a 2D space, there is a batch of points(no duplicate) in the region (0
: ,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2
: parts with half points in each .the input will be an array of points and the
: length of the array.
: struct point{
: int x;
: int y;
: };
: input : struct point * points, int length
: google了一下，说是Linear Perceptron algorithm可以解决，但找到的Linear
|
r****o
发帖数: 1950 | 4 呵呵，如果所有的点都排在你想找的那条Median线上，这方法就不灵了。
【在 x******3 的大作中提到】
: 看看这样行不
: 把所有点按照x或者y坐标排序，比如说按照x坐标排序， 然后找到x坐标的median， 划
: 条垂直线
|
r****o
发帖数: 1950 | 5 一个例子
(-1,0), (1,0), (2,0), (0,-1), (0,1), (0,2)
【在 r****o 的大作中提到】
: 呵呵，如果所有的点都排在你想找的那条Median线上，这方法就不灵了。
|
f****4
发帖数: 1359 | |
d*******8
发帖数: 785 | 7 那就在这条Median线上找它的Median，然后把这条线以这个Median为中心转一个很微小
的角度.....
【在 r****o 的大作中提到】
: 呵呵，如果所有的点都排在你想找的那条Median线上，这方法就不灵了。
|
x******3
发帖数: 245 | 8 旋转的话可能把已经分好的点划到另一边去
【在 d*******8 的大作中提到】
: 那就在这条Median线上找它的Median，然后把这条线以这个Median为中心转一个很微小
: 的角度.....
|
l********k
发帖数: 613 | 9 这样可以不可以呢？
先随便画一条线，把每个点投影到这条线上面，
如果所有的投影点在线上不重合，那在最中间的两个投影之间划一条垂线，这条垂线肯
定将所有的点分成两个部分；
如果有投影点重合的，就把这条线转一个小角度，直到没有重合的投影点。
(0
the
【在 f****4 的大作中提到】
: Within a 2D space, there is a batch of points(no duplicate) in the region (0
: ,0),(0,1),(1,0),(1,1), try to find a line which can divide the region to 2
: parts with half points in each .the input will be an array of points and the
: length of the array.
: struct point{
: int x;
: int y;
: };
: input : struct point * points, int length
: google了一下，说是Linear Perceptron algorithm可以解决，但找到的Linear
|
r****o
发帖数: 1950 | 10 我也不知道怎么搞定，看来这题没这么简单。
呼唤高人。
【在 f****4 的大作中提到】
: 那怎么解决啊
|
|
|
x******3
发帖数: 245 | 11 仔细想想，如果所有点都已经给定， 旋转一下是可以的，就是实现起来不那么简洁，
哪位大侠给个elegant的解法
【在 d*******8 的大作中提到】
: 那就在这条Median线上找它的Median，然后把这条线以这个Median为中心转一个很微小
: 的角度.....
|
f****4
发帖数: 1359 | 12 这个应该也算是常见题了，小尾羊能给个方向么？
谢谢 |
g*******y
发帖数: 1930 | 13 数学上来讲，旋转任意小一个角度，总能保证两边点数相等的...
，
【在 x******3 的大作中提到】
: 仔细想想，如果所有点都已经给定， 旋转一下是可以的，就是实现起来不那么简洁，
: 哪位大侠给个elegant的解法
|
r****o
发帖数: 1950 | 14 那个旋转的支点怎么取呢?
【在 g*******y 的大作中提到】
: 数学上来讲，旋转任意小一个角度，总能保证两边点数相等的...
:
: ，
|
g*******y
发帖数: 1930 | 15 从写程序上来讲，找到那条线后，找到转轴后，可以扫描所有其他不在这条线上的点，
算出夹角，得到一个
最小的夹角，那么该直线只要转动角度小于这个最小夹角不就行了，总共也就是O（N）
的复杂度吧
，
【在 x******3 的大作中提到】
: 仔细想想，如果所有点都已经给定， 旋转一下是可以的，就是实现起来不那么简洁，
: 哪位大侠给个elegant的解法
|
g*******y
发帖数: 1930 | 16 线上的若干点的median位置
比如第一次你是按所有点的y坐标划分出一条水平线 y=y0
那么这次就用x坐标找在y=y0线上的所有点的median x0
【在 r****o 的大作中提到】
: 那个旋转的支点怎么取呢?
|
r****o
发帖数: 1950 | 17 thanks a lot!
【在 g*******y 的大作中提到】
: 线上的若干点的median位置
: 比如第一次你是按所有点的y坐标划分出一条水平线 y=y0
: 那么这次就用x坐标找在y=y0线上的所有点的median x0
|
g*******y
发帖数: 1930 | 18 补充一点的就是
其实两次分别找y0 x0并不是找median
【在 g*******y 的大作中提到】
: 线上的若干点的median位置
: 比如第一次你是按所有点的y坐标划分出一条水平线 y=y0
: 那么这次就用x坐标找在y=y0线上的所有点的median x0
|
r****o
发帖数: 1950 | 19 没看明白了，那y0，x0到底是什么呢?
【在 g*******y 的大作中提到】
: 补充一点的就是
: 其实两次分别找y0 x0并不是找median
|
f****4
发帖数: 1359 | |
|
|
g*******y
发帖数: 1930 | 21 说错了，第一次找y0是所有y坐标的median
第二次找x0不一定是median，取决又有多少个点在直线上面，多少在直线下面...
【在 r****o 的大作中提到】
: 没看明白了，那y0，x0到底是什么呢?
|
r****o
发帖数: 1950 | 22 是不是先找到y=y0,
然后再判断多少点在y=y0上方，多少点在y=y0下方，多少点刚好落在y=y0上，
然后再决定x0怎么找?
【在 g*******y 的大作中提到】
: 说错了，第一次找y0是所有y坐标的median
: 第二次找x0不一定是median，取决又有多少个点在直线上面，多少在直线下面...
|
k***e
发帖数: 556 | 23 哈哈 this may not work when all points formed a cross
【在 g*******y 的大作中提到】
: 说错了，第一次找y0是所有y坐标的median
: 第二次找x0不一定是median，取决又有多少个点在直线上面，多少在直线下面...
|
g*******y
发帖数: 1930 | 24 why？这个方法找出来的是过cross中心的一条斜线啊，不正好吗
【在 k***e 的大作中提到】
: 哈哈 this may not work when all points formed a cross
|
k***e
发帖数: 556 | 25 i am not sure i totally get your method
my only concern is how you make sure exactly half points are on each side of
the line.
we can make sure for this when the slope of the line we will choose is not
equal to all the n(n-1)/2 slopes we can get from the n points
【在 g*******y 的大作中提到】
: why？这个方法找出来的是过cross中心的一条斜线啊，不正好吗
|
c****l
发帖数: 1280 | |
