John 椭球

对于一个三角形T,一定可以找到一个椭圆E,满足,E\subseteq T\subseteq 2E。对于一个平行四边形P,一定可以找到一个椭圆E^*,满足,E^*\subseteq P\subseteq \sqrt{2}E^*。由于在仿射变换下三角形,平行四边形,椭圆,线段比例都保持,所以只需要对正三角形和正方形进行证明就可以了。

实际上,John 定理断言,每一个n维凸体K都有一个相应的椭球E满足,E\subseteq K\subseteq nE。对每一个中心对称凸体C,都有一个相应的椭球E^*满足,E^*\subseteq C\subseteq \sqrt{n}E^*

为了证明 John 定理,我们需要引入 John 椭球的概念,为此需要证明 John-Loewner 椭球定理:对于任意一个n维空间中的含有内点的紧子集,存在唯一的椭球包含K,使得椭球体积达到最小,此时,称该椭球为 John 椭球。

证明(概要):利用椭球与n阶正定对称阵的联系,考虑所有包含 K 的椭球的中心和其对应的正定对称阵构成空间C_K,证明\det函数在C_K上取到最大值,存在性得证。如果\detC_K中有两个极大值点,可以通过这两个极大值点构造C_K中的元素,使得\det在该元素上的取值更大(这里需要利用\ln \detC_K上的凹性),由此导出矛盾,唯一性得证。

作为应用,我们考虑所有的GL_n(\mathbb{R})的紧子群G,令K=\cup_{g\in G}{g(B^n)},其中B^n是单位球,此时K含有内点。于是K是在任意G中元素作用下稳定,如果EK的 John 椭球,那么E在任意G中作用下也稳定(这是因为G的紧致性保证了其任意元素g的行列式为1,于是g(E)明显包含K,且体积与E相等,由 John 椭球的唯一性知E的稳定性),由此可知存在v\in GL_n(\mathbb{R}),使得对任意g\in G,有,v^{-1}gv(B^n)=B^n,故v^{-1}Gv\subseteq SO_n(\mathbb{R}),也就是说在相差一个共轭的程度上,正交群是极大的紧子群。

A Web Crawler for Renren: A Ruby Approach

Recently, I learned some basics of ruby through Why’s (Poignant) Guide to Ruby, and I wrote an automated crawler to visit the home pages of other people on renren, the Chinese version of facebook.
Here is the source code. You may save it as renren-crawler.rb.

require 'net/http'
require 'CGI'
$email = 'user@example.com' # Enter Your Renren Email
$password = 'my_password' # Enter Your Renren Password
class User
  attr_accessor :id, :depth;
  def initialize (id = $id, depth = 0)
    @id = id
    @depth = depth
  end
end
class Spider
  def initialize()
    @connect = Net::HTTP.start('www.renren.com', 80)
    resp0, body0 = @connect.post('/PLogin.do', "email=#{CGI::escape($email)}&password=#{CGI::escape($password)}&origURL=http%3A%2F%2Fwww.renren.com%2Fhome&domain=renren.com")
    resp1, body1 = @connect.get(resp0['location'], {"Cookie"=>resp0['set-cookie']})
    cookie = resp0['set-cookie'] + '; ' + resp1[ 'set-cookie' ]
    @start = User.new(230154727)
    @cookie = cookie
    @punish = 0
    @step = 0
  end
  def rands
    idlist = [@start.id]
    visited = {}
    begin
      @step += 1
      cid = idlist.last
      resp, body = @connect.get('/profile.do?id=' + cid.to_s, { "Cookie" => @cookie })
      if visited.member?(cid)
        visited[cid][:rev] += 1
      else
        username = body.match(/username(.|\n)+h1>/)
        if username
          username = username[0].delete("\n")
          username = username.slice((username.index('>')+1)...username.index('<'))
        end
        visited.merge!({cid=>{:name=>username, :rev=>0}})
      end
      print @step, '@', idlist.length, '[', visited[cid][:rev], ']', ':', "\t#", cid, "\t", visited[cid][:name]
      clist = body.scan(/profile.do\?id=\d{0,20}/).uniq
      if clist.length > 0
        @punish = 0
        clist.map!{|c| c.slice((c.index('=')+1)..-1).to_i}.delete_if{|c| c == 0 or visited.member?(c)}
        if clist.length > 0
          idlist << clist[rand(clist.length)]
        else
          idlist.delete_at(-1)
          print "\tDead End!"
        end
      else
        @punish += 1
        idlist.delete_at(-1)
        print "\tPunish?", @punish
        if (@punish > 1)
          print "\a\a\a\nENTER THE CAPTCHA IN YOUR BROWSER AND THE SPIDER WILL RETRY IN 15 SECONDS!\n"
          sleep 15
        end
      end
      print "\n"
    end while idlist.length > 0
  end
end
spider=Spider.new()
spider.rands

Here are some explanations for the code. The Spider class has a modified initialize method which uses your email address and password to get authentication. So before you run the script, you should put your own email and password in line 4 and 5 respectively.
Most of the functionality is in the rands method, here is the strategy that rands uses:

  1. It starts from a specific user. By default it will be me, but you can customize it on line 21 by replacing it with your own id.
  2. Check if there are any users that haven’t been visited on the home page that the crawler is visiting.
  3. If yes, pick one randomly and visit. Otherwise, take a step back and repeat step 2.
  4. Since Renren has a self-defense mechanism, it requires you to enter a CAPTCHA when you have visited 100 people. So when you hear 3 beeps (the spider is screaming, because it really hurts when hitting on a CAPTCHA) and see the warning, open anyone’s home page and respond to the challenge. The crawler will retry in 15 seconds. If the connection is re-established, everything goes like before, otherwise it keeps screaming.

So this is the big picture. And now, open your CMD (Windows) or Terminal (Unix based system), change your directory to where you saved the file, and rock it! (You should have ruby installed, otherwise it won’t work.)

$ ruby renren-crawler.rb

And the result goes like this:

1@1[0]:	#230154727	姜子麟
2@2[0]:	#230070920	张瑞勋
3@3[0]:	#179475049	杨冉
4@4[0]:	#229909528	卢天亮ayake
5@5[0]:	#233278906	许子岳
6@6[0]:	#239304543	黄一纯~晔
7@7[0]:	#230288268	蒋成皿——jcm
8@8[0]:	#231204752	王炫烨mrsmsr
9@9[0]:	#232148174	李欣意

Isn’t it cool? Have fun.

GraduaTee (Alpha Version)

此次设计毕业衫的Project名称为GraduaTee,是Graduate Tee的缩写,设计灵感来源于七巧板,小学老师用来数学启蒙的工具。正面主要图案为七巧板拼成的领带图案,毕业季穿个Tee略显不正式,那就配条领带吧。下方是奔跑的少年,欢欣雀跃、屁颠屁颠去领学士帽。反面文字为Finally, we graduated from SMS, PKU! 领口内为2D Manifold Studio的七巧板猫猫Logo。这个版本是Alpha版,欢迎大家提出意见。

Front (boy).
Front (girl).
Back (boy).
Back (girl).
Collar (inner).

让爱成就一切

这是一个月前给董老师和他的未婚夫做的结婚视频。今天,也就是 2011 年 6 月 6 日他们结婚了。经过董老师的授权,现在和大家分享一下他们的快乐与幸福。在此祝福他们能天长地久。

另附:土豆视频链接。除此视频外,其实还有一段采访视频,董老师觉得比较害羞,所以就没有传到线上。当然我觉得视频里董老师和田先生各种真情流露啊,说的话很实在也很在理。大家想看的话就去做做董老师的工作吧~

东方时尚

开学的时候组织大家一起抱团了东方时尚,这个名字奇葩的驾校。学车基本是一件挺简单的事情,就是路上来回要两个小时,太浪费时间了。

桩考的前一天发现考驾照必须使用身份证,而我除了身份证什么证都有。护照,学生证,户口簿,结婚证,离婚证在北京考驾照时都是没有用的,他们只认身份证。校长室的负责人很好,不是不知变通的人,在现有框架下给与最大便利,等我临时身份证一到就马上安排了一次考试。

桩训四次我就去了两次,难免心理有些忐忑,考前就在脑子里回想各种操作的场景。好不容易等到了桩考,考完发现前面还有老长的队伍在等内路考试,结果一个员工问有没有人换成宝莱车考试,可以不用等,我已然等得发毛,就报名了。当然宝莱车我从来没开过,于是慌慌张张打电话给教练,问一下和桑塔纳有什么异同,教练第一句话是:“恭喜你已经通过考试了,学校让你转成别的车,就一定保证你过的。”

因为外路考的考前训练那天,我要和涛写商铺那边的界面,培训我就没去。考前还是各种忐忑,不时听周围人说考试应该注意什么,默默记在心里。到我考试了,我们这个车应该有三个人,我理应是第二个考,结果好像因为第一个考生和谁重名了,东方时尚这边把档案搞错了,那人直接就没上车。于是我第一个开了,很顺利地通过了。回来的那段是一个女的开的,刚起步没多久,冲了几下,考官说靠边停车。但我实在看不出来这个女的开的有任何大问题可以挂她的,结果考官说因为她和我交换位置的时候,下右车没把车门关紧,而我上车是从左边上的,也不能赖我,只能说明缺乏安全意识,直接挂掉。这挂法实在太奇葩了,换作是我,估计车门没关紧之类的问题也不会特别注意的。

那天还听人聊说他上次挂掉是因为安全带没有插紧,开到一半弹出来了……

考驾照基本就是靠人品。