题目背景

ICPC2020 WF F

题目描述

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$ ($3 \le n \le 3\,000$) is the number of points in the set and $t$ ($0 \le t \le 10^9$) is the thickness of the pencil. Then follow $n$ lines, each containing two integers $x$ and $y$ ($-10^9 \le x, y \le 10^9$), 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 $10^{-2}$, and that no three input points are collinear.

输出格式

Output the maximum number of points that lie on a single "line" of thickness $t$.

题目大意

1921 年，业余考古学家 Alfred Watkins 提出了 Ley lines 的概念，指的是连接众多地理和历史名胜的直线。这些线常常与神秘的理论联系在一起，其中许多至今仍在流传。

对 Ley lines 的一个常见争议是，人们在地图上绘制的线的宽度实际上并非为 $0$，考虑到足够密集的点和足够宽的铅笔，找到连接多个地方的“线”是很容易的。为了探讨这种争议，你决定亲自在一个二维平面上亲自实践。

现在，这个二维平面上有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$，并且没有三个点在同一条直线上。你有一个宽度为 $t$ 的铅笔，你想知道你用这支铅笔画一条线，最多能够连接多少个不同的点。你可以假设在 $t$ 增加或减少 $10^{-2}$ 的情况下，答案是不会改变的。

数据范围：

• $3\leqslant n\leqslant 3000$，$0\leqslant t\leqslant 10^9$。
• $-10^9\leqslant x_i,y_i\leqslant 10^9$。

Translated by Eason_AC

4 2
0 0
2 4
4 9
3 1

3

3 1
0 10
2000 10
1000 12

2