MathLabs

第2题

平面上 40274027 个点组成的一个配置,若由 20132013 个红点和 20142014 个蓝点组成,且配置中任何三点都不共线,则称为哥伦比亚配置。画若干条直线,可将平面分成若干区域。对某个哥伦比亚配置,若一组直线满足以下两个条件,就称这组直线的排列是好的:(1) 没有一条直线经过配置中的任何点;(2) 没有一个区域同时包含两种颜色的点。求最小的 kk,使得对任意的 40274027 点哥伦比亚配置,都存在由 kk 条直线组成的好排列。
第 2/5 步:隔离一个凸包点或一对同色凸包点
通俗地说

在支撑线稍内侧放置直线,就能不经过配置点而隔离一个凸包顶点或一条小凸包边。

a line isolates one hull point\text{a line isolates one hull point}
详细分析

上界采用如下构造。若凸包有红色顶点 A,就在 A 处支撑线附近取一条直线,使只有 A 位于一侧。若凸包没有红色顶点,则所有凸包顶点均为蓝色;由于蓝点比红点多,必有相邻蓝顶点 A、B,在凸包边 AB 附近取一条直线即可恰好隔离 A、B。