logo
Redian新闻
>未名空间
>Parenting - 为人父母
>
[bssd] 散尽家财+求祝福+问问题（关于哮喘）+奔照片+结网 (转
avatar
[bssd] 散尽家财+求祝福+问问题（关于哮喘）+奔照片+结网 (转# Parenting - 为人父母
i*2
1 楼
一个面试题，上周面的，想了很久也木有想出来。
题目如下：
假设有一群朋友在一个城市里，这个城市是2维的，每一个人都有一个自己的二维坐标
例如：
ID x y
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
其中每一个id代表一个人，找出对于每一个最近的3个朋友并打印出来，例如以上的这
堆人的结果就是：
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1
要求是算法复杂度要小于n2
各位大牛有神马思路都提示一下吧，想了很久也没有很好的解决方法，有想到老师讲过
的nearest pair，但是貌似也不是很合适的方法。感觉至少算一下每两个点的距离都要
n2，然后就没有思路了。
avatar
az
2 楼
请大家百忙之中，吵架之余，帮忙看下哮喘的问题，包子请去宝宝版领
【 以下文字转载自 NextGeneration 讨论区 】
发信人: az (哥哥小弟和弟弟大哥), 信区: NextGeneration
标 题: [bssd] 散尽家财+求祝福+问问题（关于哮喘）+奔照片+结网
发信站: BBS 未名空间站 (Sat Nov 17 00:14:50 2012, 美东)
家里公司的事情忙得透不过气来，要结网一阵子，如果有问题，可以发到我的信箱来。
。。祝大家孩子都健健康康，顺顺利利的
散尽家财了，祝福弟弟健康，不要再生病，咳嗽哮喘了，希望月月健康，进步快快
问些关于哮喘的问题，如果哪位有经验，请赐教：弟弟连续大概40天内三次wheezing，
跑了两次ER，若干次诊所了。。。最近这次发病很快，之前一天是感冒症状，打喷嚏流
鼻涕，晚间很轻微的咳嗽，第二天咳嗽加重，但是也只是咳嗽，吃完晚饭开始呼吸声加
重，很快呼吸就出了问题，明显有些吃力，弟弟8点多睡了，wheezing很明显了，而且
呼吸很快，达到56次每分钟，略微有体温，咨询了护士之后，说由于呼吸频率高，体温
的原因，让立刻去ER。。。本来还犹豫，担心ER要等，被护士一说慌了，赶紧奔医院了
。。。这里说一下，小宝还是慎重些，ER没那么可怕，可能我们比较小，情况比较紧急
吧，两次ER都是几乎没等的，很快就进去做常规检查，见到护士，不久就见到医生的，
并没有在等候室里等待。。。其实不是很严重的wheezing，用了药扩张airway，过了一
段时间就缓解了，但是医生（2住院医，1正式医生）都说他们就把这样称作哮喘了，发
作2，3次就是啦，但是很多孩子可以自己Outgrow，这是后话了，我本身有哮喘，孩子
是高危，我有准备了，只是弟弟才15个月，不到16个月，实在可怜，我也是7，8岁才有
的哮喘，痛苦了10几年，深知哮喘的痛苦，看弟弟要受这份苦，真是心如刀割，心疼心
痛。。。ER的老医生说他几乎可以肯定弟弟的喘是病毒引起的，并没有任何炎症，不需
要消炎药或者抗菌素，当然老妈说我当年只要一喘，立刻就是青霉素，这里就是听诊器
就断定无炎症，不需要用药，就只是哮喘扩张气管的药和激素了。。。今天回到儿科医
生诊所，医生说弟弟这就是哮喘了，说哮喘会影响发育，要预防发生，给开了类固醇，
让一直吃（好像是吃的）到明年春天，当然长期服用类固醇是有副作用的，可能会影响
身高，不到万不得已，实在不想给弟弟吃，但是医生说哮喘对发育不好。。。医生还给
弟弟约了肺部专科医生，我想听下专科医生意见再说。。。
唠叨这么多，问题是：
1。有妈妈给小小宝（一岁多）吃类固醇的吗？真的有必要吃吗？如果是病毒引起的哮
喘，为什么吃类固醇能预防呢？今天我没去诊所，所以也没问，碰碰运气，有懂得吗？
2。哮喘影响发育是什么方面呢？
3。哮喘跟过敏有关的，考虑给弟弟做个过敏测试，谁有经验呢？真的有必要没，困惑
啊。。。我自己是过敏体质，弟弟多半是遗传了。。。可是医生很肯定弟弟是病毒引起
的哮喘呢？
有孩子哮喘频繁发作，后来Outgrow的给传授点经验吗？我都有点怕带弟弟出门了，唉
。。。
保佑我可爱的弟弟不要再生病了，用什么换我都愿意。。。
avatar
b*e
3 楼
全部点按照X坐标排序，O(NlogN) , 然后就好办了。
avatar
k*e
4 楼
big bless
avatar
H*e
5 楼
这不是k-nearest neighbors吗
有成熟算法吧

【在 i********2 的大作中提到】
: 一个面试题，上周面的，想了很久也木有想出来。
: 题目如下：
: 假设有一群朋友在一个城市里，这个城市是2维的，每一个人都有一个自己的二维坐标
: 例如：
: ID x y
: 1 0.0 0.0
: 2 10.1 -10.1
: 3 -12.2 12.2
: 4 38.3 38.3
: 5 79.99 179.99
avatar
l*a
6 楼
不懂
不过不赖司一下

【在 az 的大作中提到】
: 请大家百忙之中，吵架之余，帮忙看下哮喘的问题，包子请去宝宝版领
: 【 以下文字转载自 NextGeneration 讨论区 】
: 发信人: az (哥哥小弟和弟弟大哥), 信区: NextGeneration
: 标 题: [bssd] 散尽家财+求祝福+问问题（关于哮喘）+奔照片+结网
: 发信站: BBS 未名空间站 (Sat Nov 17 00:14:50 2012, 美东)
: 家里公司的事情忙得透不过气来，要结网一阵子，如果有问题，可以发到我的信箱来。
: 。。祝大家孩子都健健康康，顺顺利利的
: 散尽家财了，祝福弟弟健康，不要再生病，咳嗽哮喘了，希望月月健康，进步快快
: 问些关于哮喘的问题，如果哪位有经验，请赐教：弟弟连续大概40天内三次wheezing，
: 跑了两次ER，若干次诊所了。。。最近这次发病很快，之前一天是感冒症状，打喷嚏流
avatar
f*t
7 楼
上次有人说k-d tree
avatar
p*5
8 楼
我妹妹小的时候有哮喘，是在吃了学校建议买的智力碘引发的，当时只有7-8岁。以后
有时发作，吃一种药，就可以了。我有空去问问她药名。就是第一次住了院，以后就是
发作时吃点药。发育后就不再发病了，现在挺好的一个人。
我帮你问问。祝福。
avatar
r*t
9 楼
成熟算法 < O(N^2) 么？

【在 H***e 的大作中提到】
: 这不是k-nearest neighbors吗
: 有成熟算法吧
avatar
s*3
10 楼
没有经验，祝好运，希望宝宝早日没事
avatar
v*a
11 楼
或许可以这样：
构造 Voronoi Diagram, O(NLogN) 可以构造出来
Voronoi 最多有 3N 条边
求每个点最近的点，只需要检查每条 voronoi的边，O(2 * 3N )
求每个点最近的2个点，除了检查每条边，还要检查，离他最近点的所有voronoi的边，
O(? * 3N), ? is constant,
求最近的3个点，还要检查第二近的点的所有边，以及第一近的点的所有voronnoi的边
，可以证明肯定在这些边里，O(? * 3N), ? is also constant.
Anyway, O(NLogN）
请问你面的什么公司？
这种计算几何的题目，估计 G/FB 也不会考的吧，做地图的公司？
如果还有position的话，也想投一下试试，
投了无数公司，现在一个面试都没有……杯具啊
avatar
l*f
12 楼
bless bless
口服类固醇可能是prednisolone之类吧，你可以查查wiki, 或者mayo clinic, 好像是
通过bind G receptors , 从而suppress inflammatory reaction来减轻症状, 感觉算
是哮喘常规药，不过狠难吃，我们家我自己和两娃都开过这药，老大是春天过敏咳漱，
有一次比较厉害医生也除了喷喉咙的那个hfa inhaler，还要口服这个几次，老二是因
为过敏，不过他一吃就吐，后来就没喂//汗
不过这些都是治表不治本的。。。。哮喘这个医生认为也是一种过敏反应，不过小宝宝
过敏源很难测，我家老二上次去看的过敏医生是这么认为滴。建议还是少出门，家里空
气啊接触环境啊尽量按哮喘标准处理。。。。
还有医生可能说是病毒性感冒trigger哮喘吧，看这里
http://www.mayoclinic.com/health/asthma/AS00024

【在 az 的大作中提到】
: 请大家百忙之中，吵架之余，帮忙看下哮喘的问题，包子请去宝宝版领
: 【 以下文字转载自 NextGeneration 讨论区 】
: 发信人: az (哥哥小弟和弟弟大哥), 信区: NextGeneration
: 标 题: [bssd] 散尽家财+求祝福+问问题（关于哮喘）+奔照片+结网
: 发信站: BBS 未名空间站 (Sat Nov 17 00:14:50 2012, 美东)
: 家里公司的事情忙得透不过气来，要结网一阵子，如果有问题，可以发到我的信箱来。
: 。。祝大家孩子都健健康康，顺顺利利的
: 散尽家财了，祝福弟弟健康，不要再生病，咳嗽哮喘了，希望月月健康，进步快快
: 问些关于哮喘的问题，如果哪位有经验，请赐教：弟弟连续大概40天内三次wheezing，
: 跑了两次ER，若干次诊所了。。。最近这次发病很快，之前一天是感冒症状，打喷嚏流
avatar
i*e
13 楼
这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
高性能。
把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
avatar
az
14 楼
我们医生是要求长期服用，一直到明年春天
能说说环境按哮喘处理是什么意思呢？
谢谢

【在 l*****f 的大作中提到】
: bless bless
: 口服类固醇可能是prednisolone之类吧，你可以查查wiki, 或者mayo clinic, 好像是
: 通过bind G receptors , 从而suppress inflammatory reaction来减轻症状, 感觉算
: 是哮喘常规药，不过狠难吃，我们家我自己和两娃都开过这药，老大是春天过敏咳漱，
: 有一次比较厉害医生也除了喷喉咙的那个hfa inhaler，还要口服这个几次，老二是因
: 为过敏，不过他一吃就吐，后来就没喂//汗
: 不过这些都是治表不治本的。。。。哮喘这个医生认为也是一种过敏反应，不过小宝宝
: 过敏源很难测，我家老二上次去看的过敏医生是这么认为滴。建议还是少出门，家里空
: 气啊接触环境啊尽量按哮喘标准处理。。。。
: 还有医生可能说是病毒性感冒trigger哮喘吧，看这里
avatar
r*t
15 楼
discretization 只能近似吧，方格子按层数算距离有很大误差。

【在 i**********e 的大作中提到】
: 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
: 高性能。
: 把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
: 么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
: 任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
avatar
p*5
16 楼
氨茶碱

【在 p********5 的大作中提到】
: 我妹妹小的时候有哮喘，是在吃了学校建议买的智力碘引发的，当时只有7-8岁。以后
: 有时发作，吃一种药，就可以了。我有空去问问她药名。就是第一次住了院，以后就是
: 发作时吃点药。发育后就不再发病了，现在挺好的一个人。
: 我帮你问问。祝福。
avatar
i*e
17 楼
我想了一下，有个edgecase，就是最近的三个点不一定是格子里边的点，有可能是格子
旁边的。所以附近的一些格子也必须搜索。

【在 r****t 的大作中提到】
: discretization 只能近似吧，方格子按层数算距离有很大误差。
avatar
l*f
18 楼
是，可能是怕秋冬感冒多容易引发哮喘吧
家里就是尽量去除可能过敏源，关窗，室内最好地板，不要有毛绒动物，去尘，床单什
么的注意隔绝杀死螨虫，有的家里还用空气过滤器，不过这个我没有用过

【在 az 的大作中提到】
: 我们医生是要求长期服用，一直到明年春天
: 能说说环境按哮喘处理是什么意思呢？
: 谢谢
avatar
H*e
19 楼
觉得这个不work，你search到不管哪一层都无法断定就此停止

【在 i**********e 的大作中提到】
: 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
: 高性能。
: 把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
: 么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
: 任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
avatar
az
20 楼
哦，谢谢。我家从来不开窗，汗，全木地板，一片地毯都没有，我是过敏体质，肯定不
用地毯的。。。没动物，好，明天就洗被褥去。。。空气过滤器真有一个，不大，不可
能管全家的，不晓得有没有管全家的？要不要请人清洗管道啥的？我家才换的空调，安
装的人说管道挺干净的，不脏。。。还有什么要注意的呢？
能问下，你的孩子长期吃过类固醇吗？多大吃的？

【在 l*****f 的大作中提到】
: 是，可能是怕秋冬感冒多容易引发哮喘吧
: 家里就是尽量去除可能过敏源，关窗，室内最好地板，不要有毛绒动物，去尘，床单什
: 么的注意隔绝杀死螨虫，有的家里还用空气过滤器，不过这个我没有用过
avatar
i*2
21 楼
那你这相当于把这个看做一张图 按单位半径增长穷举搜索么？
这个复杂度就和n没关系了吧 和数值之间的差距有关系 也就是最小半径和最大半径？
那么应该是n*k 我觉得是一定情况下比n*n小 但是要看点的稀疏程度
我的理解对么？

【在 i**********e 的大作中提到】
: 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
: 高性能。
: 把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
: 么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
: 任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
avatar
l*f
22 楼
啊，那你家已经很高标准了
没有，我家娃没吃过这么长的，老大原来主要是湿疹，皮肤过敏的问题
春天才季节过敏，上次是因为踢球引起的，就吃了几天

【在 az 的大作中提到】
: 哦，谢谢。我家从来不开窗，汗，全木地板，一片地毯都没有，我是过敏体质，肯定不
: 用地毯的。。。没动物，好，明天就洗被褥去。。。空气过滤器真有一个，不大，不可
: 能管全家的，不晓得有没有管全家的？要不要请人清洗管道啥的？我家才换的空调，安
: 装的人说管道挺干净的，不脏。。。还有什么要注意的呢？
: 能问下，你的孩子长期吃过类固醇吗？多大吃的？
avatar
i*2
23 楼
一个东部的startup，一共十个人的公司
估计你兴趣不大啊，算是找实习，不是fulltime

【在 v***a 的大作中提到】
: 或许可以这样：
: 构造 Voronoi Diagram, O(NLogN) 可以构造出来
: Voronoi 最多有 3N 条边
: 求每个点最近的点，只需要检查每条 voronoi的边，O(2 * 3N )
: 求每个点最近的2个点，除了检查每条边，还要检查，离他最近点的所有voronoi的边，
: O(? * 3N), ? is constant,
: 求最近的3个点，还要检查第二近的点的所有边，以及第一近的点的所有voronnoi的边
: ，可以证明肯定在这些边里，O(? * 3N), ? is also constant.
: Anyway, O(NLogN）
: 请问你面的什么公司？
avatar
m*7
24 楼
bless bless!
avatar
i*2
25 楼
请问然后就好办了是什么意思？
当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
，然后呢？
能给点细节么？

【在 b*****e 的大作中提到】
: 全部点按照X坐标排序，O(NlogN) , 然后就好办了。
avatar
c*k
26 楼
我们家娃的床上用品一周至少洗一次,高温消毒档洗. 我们有一个空气过滤器放在小朋
友的房间, 你也可以用whole house air purifier, 外接在空调上的.
air purifier高端到低端有很多种, 相差挺大的. 比较好的牌子有IQ Air, Blue Air等
等.
还有比较简单便宜的办法就是更换AC filter cabinet, 可以安装media filter, 那个
过滤的比较干净, 当然和好的air purifier是不能比的, 但是效果可以叠加.
duct cleaning基本是不需要的.
我们家娃是哮喘高危人群, 现在还没有发作, 我们很担心她这个冬天会发作. 这些都是
从网上看来的预防哮喘的经验总结.

【在 az 的大作中提到】
: 哦，谢谢。我家从来不开窗，汗，全木地板，一片地毯都没有，我是过敏体质，肯定不
: 用地毯的。。。没动物，好，明天就洗被褥去。。。空气过滤器真有一个，不大，不可
: 能管全家的，不晓得有没有管全家的？要不要请人清洗管道啥的？我家才换的空调，安
: 装的人说管道挺干净的，不脏。。。还有什么要注意的呢？
: 能问下，你的孩子长期吃过类固醇吗？多大吃的？
avatar
i*2
27 楼
你所说的成熟的算法具体是什么呢？
我有查到一些idea，但是也没有具体的复杂度什么的，
因为这个题目是要求给一个小时 让把代码写出来 然后发回去 当时一个小时也没写出
来...
请问具体实现是怎么实现呢？

【在 H***e 的大作中提到】
: 这不是k-nearest neighbors吗
: 有成熟算法吧
avatar
w*t
28 楼
完全不懂，BIG BLESS...........
如果是我，可能选择先吃药，然后尽快约专科医生
感觉专科医生应该比儿医和ER的要好一些
avatar
v*a
29 楼
你是要写代码？还是设计 < O(N^2)的算法？这2个是不一样的

【在 i********2 的大作中提到】
: 你所说的成熟的算法具体是什么呢？
: 我有查到一些idea，但是也没有具体的复杂度什么的，
: 因为这个题目是要求给一个小时 让把代码写出来 然后发回去 当时一个小时也没写出
: 来...
: 请问具体实现是怎么实现呢？
avatar
l*a
30 楼
从不开窗会不会也不好？我觉得还是需要换气的吧，还有，有太阳的时候就把被子什么
的晒晒，会把螨虫杀死。
我不知道你老二有没有过敏体质，一般的路线就是过敏-〉湿疹-〉哮喘。所以从根子上
来说，还是过敏。我的建议是食物上尽可能的杂，尽量让孩子多吃点，身体好了就会慢
慢好了。

【在 az 的大作中提到】
: 哦，谢谢。我家从来不开窗，汗，全木地板，一片地毯都没有，我是过敏体质，肯定不
: 用地毯的。。。没动物，好，明天就洗被褥去。。。空气过滤器真有一个，不大，不可
: 能管全家的，不晓得有没有管全家的？要不要请人清洗管道啥的？我家才换的空调，安
: 装的人说管道挺干净的，不脏。。。还有什么要注意的呢？
: 能问下，你的孩子长期吃过类固醇吗？多大吃的？
avatar
i*e
31 楼
几年前写的程序，忘了。基本思路是分成 n_w x n_h 个格子没错。
n_w 是多少个 column，n_h 是多少个 row.
然后生成 buckets:
bucket = new list[n_w*n_h];
把每个点 hash 到相对的格子去:
temp_pt.x = coor_x[i]; temp_pt.y = coor_y[i]; temp_pt.id = i;
int col = (int)((coor_x[i] - min_x) / j);
int row = (int)((coor_y[i] - min_y) / k);
int index = row * n_w + col;
bucket[index].push_back(temp_pt);
然后就是搜索的算法了，用 visited table 来记录搜过的格子，然后一层一层往外搜
。当时没考虑可读性，写的比较乱，请见谅。
http://ideone.com/suHFu

【在 i********2 的大作中提到】
: 那你这相当于把这个看做一张图 按单位半径增长穷举搜索么？
: 这个复杂度就和n没关系了吧 和数值之间的差距有关系 也就是最小半径和最大半径？
: 那么应该是n*k 我觉得是一定情况下比n*n小 但是要看点的稀疏程度
: 我的理解对么？
avatar
az
32 楼
一一谢过楼上各位，帖子我都认真阅读了，感谢
avatar
q*x
33 楼
按x/y分别排序。
任何一个点只需检查其x坐标上下六个和y坐标上下六个点。
这样是O(nlogn)+O(12n) = O(nlgn)。

【在 i********2 的大作中提到】
: 一个面试题，上周面的，想了很久也木有想出来。
: 题目如下：
: 假设有一群朋友在一个城市里，这个城市是2维的，每一个人都有一个自己的二维坐标
: 例如：
: ID x y
: 1 0.0 0.0
: 2 10.1 -10.1
: 3 -12.2 12.2
: 4 38.3 38.3
: 5 79.99 179.99
avatar
i*e
34 楼
这不对，我举了个反例（看贴图）。
X1,X2,X3 是 X标上下最近的三个点，Y1,Y2,Y3 是Y 标上下最近的三个点（你可以自由
添加到六个点也行）。
但是 Z 确是最近的点。当然，我可以在 Z 同样的位置自由添加多两个点。那么，最近
的三个点都不在 X1..X6 和 Y1... Y6 。

【在 q****x 的大作中提到】
: 按x/y分别排序。
: 任何一个点只需检查其x坐标上下六个和y坐标上下六个点。
: 这样是O(nlogn)+O(12n) = O(nlgn)。
avatar
q*x
35 楼
你理解有误。Z点的x/y坐标投影显然比x1,x2,x3和y1,y2,y3更近。
数学上很容易证明。
对于任意一点p(x,y)，假设：
a1，a2，a3是x坐标小于p.x的点里x坐标最大的三个点；
a4，a5，a6是x坐标大于p.x的点里x坐标最小的三个点；
类似定义b1~b6，关于y坐标。
那么距离p最近的三个点一定在a1~6和b1~6里。这样只需查12个点。

【在 i**********e 的大作中提到】
: 这不对，我举了个反例（看贴图）。
: X1,X2,X3 是 X标上下最近的三个点，Y1,Y2,Y3 是Y 标上下最近的三个点（你可以自由
: 添加到六个点也行）。
: 但是 Z 确是最近的点。当然，我可以在 Z 同样的位置自由添加多两个点。那么，最近
: 的三个点都不在 X1..X6 和 Y1... Y6 。
avatar
i*e
36 楼
请看我贴的新图，帮忙看看哪里有误。
根据我的理解：
X1,X2,X3 是 x 坐标 小于 P.x 最大的三个点，
X4,X5,X6 是 x 坐标 大于 P.x 最小的三个点。
类似于 Y1,...Y6.
我肯定漏掉了一些重要的信息，如果理解有误请耐心指教，谢谢!

【在 q****x 的大作中提到】
: 你理解有误。Z点的x/y坐标投影显然比x1,x2,x3和y1,y2,y3更近。
: 数学上很容易证明。
: 对于任意一点p(x,y)，假设：
: a1，a2，a3是x坐标小于p.x的点里x坐标最大的三个点；
: a4，a5，a6是x坐标大于p.x的点里x坐标最小的三个点；
: 类似定义b1~b6，关于y坐标。
: 那么距离p最近的三个点一定在a1~6和b1~6里。这样只需查12个点。
avatar
q*x
37 楼
good catch. you are right. my conclusion is wrong.
i think my 12 points （actually, 6) can serve as filter to narrow down the search.
assume the interested point is (0,0), if x^2+y^2 <= x1^2+y1^2, we must have
x < x1 || y < y1. if x1 is already the min, any point whose y is bigger than
y1 is eliminated.

【在 i**********e 的大作中提到】
: 请看我贴的新图，帮忙看看哪里有误。
: 根据我的理解：
: X1,X2,X3 是 x 坐标 小于 P.x 最大的三个点，
: X4,X5,X6 是 x 坐标 大于 P.x 最小的三个点。
: 类似于 Y1,...Y6.
: 我肯定漏掉了一些重要的信息，如果理解有误请耐心指教，谢谢!
avatar
a*m
38 楼
有。 n层最远的点距离也不会超过n+2层最近的点。

【在 H***e 的大作中提到】
: 觉得这个不work，你search到不管哪一层都无法断定就此停止
avatar
b*e
39 楼

先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化


【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
avatar
b*e
40 楼

先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化

【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
avatar
b*e
41 楼

先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化

【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
avatar
b*e
42 楼

先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化

【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
相关阅读
分享 Amazon Prime Account请教小娃在外面捡到钱该咋办？H1N1 或类似的病毒性感冒今天娃说，爸爸我爱你，你骂我我也爱你。新年夸我儿子， 希望马年大顺。大家推荐几个适合三岁半，四岁女孩子玩的game吧ObamaCare恐崩盘，哪一些条款奥巴马不想让你知道？ (转载)右右5岁了请问上一年半K 会有什么影响吗，谢谢七岁小孩150度的近视该戴眼镜吗？95129附近真心求推荐preschool~孩子在不同年龄阶段玩的游戏（图）小孩打球是用的眼镜是什么样的?Re: 不牛海龟想游回来Orion University一所学校感兴趣启动围棋数学项目大家car seat harness clip断了怎么处理的？给孩子学习中文的36个免费资源（zz）三岁女儿发烧转成肺炎，高烧不退，怎么办？ (转载)美妈们给推荐个物美价廉的booster car seat吧？6岁(grade 1) 女孩受到Racist Language 攻击, 请大家帮忙
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。