HBC232544[JLOI2014]松鼠的新家,数据结构,线段树,树链剖分[2020WF]Ley Lines题解（theamateurarchaeologist）

凸凸曼凸凸算法基础篇 2023-11-09 17:29:01 36 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

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)(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?

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)(x, y)(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?