Monthly Archives: June 2009

《影响力》

昨天晚上在网友小艺兄的推荐下看了《影响力》这本书。话说这种书果然比数学书或者码农书读起来轻松,花了一个晚上+一个半天的时间居然就读完了,感觉收获不小。

简单来说,作者的理论是,和动物的某些本能行为类似,人类也有一种几乎是与生俱来的在某种情况下的反应,尽管这种反应在认真的思考之后会发现很不可思议甚至可以说很愚蠢,但我们在大多数情况下还是会这么做,因为生活经验告诉我们这样做在通常情况下是对的,结果这就可以被“别有用心”(出于善意或恶意)的人利用来达成自己的目的。

作者把这些情况分成了六大类,并给出了很多具体的案例与实验结果。关于具体的例子我就不详细说了,只说一个有意思的小实验,说把一个人的正常照片和左右交换后的照片同时拿出来,让被实验者选择更喜欢的,结果发现这个人的朋友选择的是正常的照片,而这个人自己选择的是左右相反的照片,因为他更熟悉的是那个镜子里的自己,由此体现出作者要论证的“熟悉导致喜好感”。这个结论我想是很有道理的,一个很常见的现象是,随着时间的推移,本来第一印象一般的女同学会变得越来越漂亮起来-_- 另外关于照片说句跑题的,在有很多人的集体照中,我往往找不到自己,但是能很快找到别的认识的人,不知道别人有这个情况不。

三省吾身之比赛的理由

前言:发现剖析自己的不正常心理是很有意思的事,故有了这个“三省吾身”系列。

今天的“有道难题”比赛做挂了,心里有点小不爽,仔细分析了一下我不爽的来由,随便记一下。

在ACM以及类ACM的训练和比赛里,成绩是很容易量化为OJ切题数和比赛名次的,并且随着自己的努力,这些数值一般来说总会提升,而在其他的地方自己的努力就往往不会体现得很明显,于是我往往会沉溺其中来获取满足感。尤其是当我在这方面已经达到了一个相对较高的水平时,满足感也会来得相对较易:比起从一摞书本或是一坨Paper里学到一点让人豁然开朗的知识,在比赛中拿个说得过去的名次要容易得多。所以我在退役以后还经常参加一些比赛,表面上是对ACM仍有留恋,实际不过是追求一点满足感而已。另一方面,如果我在比赛中竟然没有拿到想要的成绩时,失落感也就格外强烈,我想这就是今晚我比较不爽的原因。

其实按理说,我在这方面的能力无需再用更多的证明,我应该可以做到完全不关心名次之类的东西的,可惜我仍然做不到。有争胜心不是坏事,但当争胜变成了虚荣,比赛只是为了在Rank的前几名有我的ID时,我的比赛已经变味了。

综上,一方面应该多在其他方面寻求进步,不能沉溺于过去[也许勉强算的上]的成绩中,哪怕在其他方面的进步困难重重,想想自己在ACM上的起步不也是一样?另一方面在参加类似的算法比赛时的心态要正确,不为证明自己,不为荣誉和奖励,只为求知,只为快乐。

说起来容易做起来难啊,呵呵。

直线交点的凸包(百度之星2009初赛第二场第三题)

题意很简单,给n条直线,求包围这n条直线的所有交点的凸包。因为交点的数量级在O(n^2),而这题的n是100000,所以朴素的写法是不能过大数据的。

高效算法的基本思路就是尽量先排除肯定不在凸包上的点,只考虑那些有可能在凸包上的点。首先我们考虑没有任何两条直线平行的情况。算法实际上很简单,先将直线按斜率排序,只要排成一圈即可,哪一条在最前面无所谓。设直接为{L1,L2,…,Ln}然后,只需考虑所有相邻直线L_i与L_{i+1}(包括Ln与L1)的交点即可,这样的交点共有O(n)个,然后再用O(nlogn)的算法求凸包。故总的复杂度为O(nlogn)。

如下图所示,四条直线,只需考虑四个红色交点即可。

chull

算法证明直观描述如下:显然,对于组成凸包的每条线段而言,所有的交点都在这条线段的同侧(或在这线段上)。分两种情况考虑凸包上的线段:

(1) 这线段是原有直线的一部分。因为所有交点都在其一侧,可以发现,这些直线在其另一侧是呈“放射状”的,故凸包线段两端的点,一定是该直线与最上和最下(也即斜率与该直线最接近的两条)直线的交点。

(2) 这线段不是原有直线的一部分。在这种情况下,线段的两端一定是某两条直线的交点,而这两条直线一定也是斜率相邻的。不然的话,若有一条直线的斜率在两者之间,则一定会有一个交点交到凸包这条线的另一侧。(这里感觉不好说清楚……)

最后再加入平行直线的情况。对于一组平行直线,容易发现只需考虑最“外侧”的两条即可。这样的话,原来的一条直线最多变成两条线,故原来的一个交点最多变成四个点,但这只是一个常数倍数,所以时间复杂度不变。

本文缩写自胡伟栋大牛的一篇文章,在此表示感谢。

本Blog停机维护一天

如题。