时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
兰德索尔大陆的骑士们最近遇到了一个大麻烦。
近日来,兰德索尔大陆的边境不断受到不明魔物军队的攻击,因此骑士们决定在兰德索尔大陆上修筑一些瞭望塔,以便在魔物来袭时,能够及时将消息传递到皇室和军营中。
为了简化问题,我们可以将瞭望塔的修筑过程和修筑要求,描述为如下的二维

坐标系中的问题:
兰德索尔皇室的位置位于原点
)
处,军营位于

轴上一点
)
处。骑士们在第一象限内选择了

个候选点
%2C%20(x_1%2C%20y_1)%2C%20...%2C%20(x_%7Bn-1%7D%2C%20y_%7Bn-1%7D))
,他们将在这

个点中,挑选若干个点修筑瞭望塔。
为了保证瞭望塔之间能够正常地项皇室和军营传递消息,任意两个瞭望塔向皇室和军营通信的信道不能够产生干扰。因此,瞭望塔的修筑选址必须符合以下要求:对于任意两个位于点
)
和位于点
)
的瞭望塔,若

,则点

应该严格位于

内。(换句话说,就是

应该位于

内,
且两个三角形之间只能共享 OA 这一条边。)
修筑一座瞭望塔需要耗费许多玛那(兰德索尔大陆的货币),而骑士们并不想耗费太多的预算,因此他们只想在

个候选点中,找到满足上述包含关系最多的
一组点,在这些位置上修筑瞭望塔。但是兰德索尔大陆的数学和几何水平并不发达,因此骑士们希望你帮他们找到
最多的一组点,使这些点符合修筑瞭望塔的条件,并告诉他们这组点的个数最大可以是多少。
输入描述:
每个测试点包含多组数据,请处理到文件结束。
每组测试数据的第一行有两个整数
和
,表示骑士们选定的候选点个数
,以及军营所处位置
的坐标。
接下来有
行,每一行包含两个整数
,表示第
个候选点的位置。
保证单个测试点的所有测试数据中,候选点的个数之和

。
保证所有的坐标数据(
)都在 int 的范围之内,且任意两个点不重复。
输出描述:
对于每组测试数据,在单独的一行内输出一个整数,表示所给的
个点中,满足修筑包含关系的最多的一组点。
示例1
输入
复制
2 4
2 1
4 2
3 4
2 2
2 3
1 3
5 4
2 1
4 2
2 2
1 2
2 3
5 5
1 1
2 2
3 3
4 4
5 5