兰德索尔的瞭望塔
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

兰德索尔大陆的骑士们最近遇到了一个大麻烦。

近日来,兰德索尔大陆的边境不断受到不明魔物军队的攻击,因此骑士们决定在兰德索尔大陆上修筑一些瞭望塔,以便在魔物来袭时,能够及时将消息传递到皇室和军营中。

为了简化问题,我们可以将瞭望塔的修筑过程和修筑要求,描述为如下的二维 坐标系中的问题:

兰德索尔皇室的位置位于原点 处,军营位于 轴上一点 处。骑士们在第一象限内选择了 个候选点,他们将在这 个点中,挑选若干个点修筑瞭望塔。

为了保证瞭望塔之间能够正常地项皇室和军营传递消息,任意两个瞭望塔向皇室和军营通信的信道不能够产生干扰。因此,瞭望塔的修筑选址必须符合以下要求:对于任意两个位于点 和位于点 的瞭望塔,若,则点 应该严格位于 内。(换句话说,就是 应该位于 内,且两个三角形之间只能共享 OA 这一条边。)

修筑一座瞭望塔需要耗费许多玛那(兰德索尔大陆的货币),而骑士们并不想耗费太多的预算,因此他们只想在 个候选点中,找到满足上述包含关系最多的一组点,在这些位置上修筑瞭望塔。但是兰德索尔大陆的数学和几何水平并不发达,因此骑士们希望你帮他们找到最多的一组点,使这些点符合修筑瞭望塔的条件,并告诉他们这组点的个数最大可以是多少。

输入描述:

每个测试点包含多组数据,请处理到文件结束。

每组测试数据的第一行有两个整数 ,表示骑士们选定的候选点个数,以及军营所处位置 的坐标。

接下来有 行,每一行包含两个整数 x_i, y_i,表示第 个候选点的位置。

保证单个测试点的所有测试数据中,候选点的个数之和

保证所有的坐标数据(x_i, y_i)都在 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

输出

复制
1
2
3
1

说明

输入样例包含四组测试数据。

第一组测试数据如下图所示。由于两个点不严格包含(除\ OA 外有其它公共边),故每组最多只能选择在\ 1 个点上建瞭望塔,答案为 1.

第二组测试数据如下图所示。满足包含关系最多的一组点有两个,即\ B 点和\ C\ B, D 两点并不满足包含关系,故答案为 2.


第三组测试数据如下图所示。满足包含关系最多的一组点为\ B, C, D,故答案为 3.


第四组测试数据如下图所示。由于任意两个点都不满足严格包含的条件,故每组最多只能选择在 1 个点上建瞭望塔,答案为 1.