[2020WF]Ley Lines
题号:NC232544
时间限制:C/C++/Rust/Pascal 15秒,其他语言30秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

In 1921, the amateur archaeologist Alfred Watkins coined the term ``ley lines'' to refer to straight lines between numerous places of geographical and historical interest. These lines have often been associated with mysterious and mystical theories, many of which still persist.

One of the common criticisms of ley lines is that lines one draws on a map are actually of non-zero width, and finding ``lines'' that connect multiple places is trivial, given a sufficient density of points and a sufficiently thick pencil. In this problem you will explore that
criticism.

For simplicity, we will ignore the curvature of the earth, and just assume we are dealing with a set of points on a plane, each of which has a unique (x, y) coordinate, and no three of which lie on a single straight line. Given such a set, and the thickness of your pencil,
what is the largest number of points through which you can draw a single line?

输入描述:

The first line of input consists of two integers n and t, where n () is the number of points in the set and t () is the thickness of the pencil.
Then follow n lines, each containing two integers x and y (), indicating the coordinates of a point in the set.
You may assume that the input is such that the answer would not change if the thickness t was increased or decreased by , and that no three input points are collinear.

输出描述:

Output the maximum number of points that lie on a single ``line'' of thickness t.
示例1

输入

复制
4 2
0 0
2 4
4 9
3 1

输出

复制
3
示例2

输入

复制
3 1
0 10
2000 10
1000 12

输出

复制
2