继上次的硬币游戏（解答在此）之后，Sariel又出了一个有意思的题目。
给定平面上若干个点。证明总存在一个黑白染色方法，使得对于平面上任何一个直线，若此直线这一侧有多于50个点，则此侧的点颜色不完全一样。
更多：
答案呢？
求出点集的凸包，设这些点按凸包的顺序依次为1,2..k，将标号为奇数的点染黑色，标号为偶数的点染白色。对于相邻的三个点x-1,x,x+1，若由它们组成的三角形（不包括线段)内存在别的点，则这些点染与点x不同的颜色。 可能有一些细节问题，如共线，重点等。 ps:I am an OIer
Ph.D Candidate from iTCS & CASTU, Tsinghua Univeristy, major in Applied Mathematics (Theoretical Computer Science)
This blog focuses on (computer) science, reviews( books), blog(WordPress), personal thinking and stuffs. Now it has 503 articles, 9,635 comments, and 3000+ subscribers (why and how to subscribe?)
New comer could start from here
Contact me by Email
答案呢？
求出点集的凸包，设这些点按凸包的顺序依次为1,2..k，将标号为奇数的点染黑色，标号为偶数的点染白色。对于相邻的三个点x-1,x,x+1，若由它们组成的三角形（不包括线段)内存在别的点，则这些点染与点x不同的颜色。
可能有一些细节问题，如共线，重点等。
ps:I am an OIer