继上次的硬币游戏(解答在此)之后,Sariel又出了一个有意思的题目。
给定平面上若干个点。证明总存在一个黑白染色方法,使得对于平面上任何一个直线,若此直线这一侧有多于50个点,则此侧的点颜色不完全一样。
更多:
写于2008年八月 20日
答案呢?
求出点集的凸包,设这些点按凸包的顺序依次为1,2..k,将标号为奇数的点染黑色,标号为偶数的点染白色。对于相邻的三个点x-1,x,x+1,若由它们组成的三角形(不包括线段)内存在别的点,则这些点染与点x不同的颜色。 可能有一些细节问题,如共线,重点等。 ps:I am an OIer
Sariel是什么人?
80后,科学青年;宅居动物;习惯用Google获取信息,靠Gmail保持联系;喜欢解决问题;死理性,不太文艺
邮件联系,订阅RSS到Google Reader
答案呢?
求出点集的凸包,设这些点按凸包的顺序依次为1,2..k,将标号为奇数的点染黑色,标号为偶数的点染白色。对于相邻的三个点x-1,x,x+1,若由它们组成的三角形(不包括线段)内存在别的点,则这些点染与点x不同的颜色。
可能有一些细节问题,如共线,重点等。
ps:I am an OIer
Sariel是什么人?