现在二维坐标系里面有n个据点,第i个据点的坐标为(xi,yi)。
现在要在这些据点当中挑选一部分来修建驿站，驿站的作用范围为半径r。

现在要求得出修建驿站的最小个数，使所有据点都在驿站的作用范围里面。
为了使题目简化，现在规定驿站只能修建在据点上和驿站作用范围的边界也包含在内。

输入:
第一行输入两个数，第一个数是据点个数n，第二个数是驿站的作用范围r，两个输入之间用空格隔开。

然后接下来n行每行输入两个数，第一个数是第i个驿站的横坐标，第二个数是第i个驿站的纵坐标，两个输入之间用空格隔开。
输出:一行，所修建驿站的最小个数。

例子:
输入:
9 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
输出:
3

这题虽然没有去敲代码~思路还是有的~不过感觉效率不太高。
先在想到思路是用组合从底层到高层递推穷举~这样虽然可以做出来~不过感觉效率较低~有没有一个高效的算法~和最好给出一个修建驿站的方案~~~~

[此贴子已经被作者于2017-4-21 12:47编辑过]

其实这题和求圆包含点集的元素最大个数是出自同一条题目的~这题原来是不要求驿站一定要修建在据点上~不过出题的说这样难度太大就把它分解成两个问题，不过即使是这样还是做不出来~我们这边几乎没有人能做出来啊~~~

最近被出题的斥说自己的算法有多厉害~~结果拿了这题目出来~结果遇到很多不会处理的地方~~~被打击了~~~
结果感觉自己很渺小~~

最近其它科目准备测验了~打算先放下了~~
这里要告诫各位~~就算自己感觉挺有能力都好也不要吹嘘自己啊~现在拿了这么一条棘手的题目~降低难度后还是做不出来被训斥简直崩溃了~~~

现在打算先放下吧~虽然认真想想看还是会有进展的~不过还得先补补其它科目~

这题还是留给有能力的来看看吧~~~~~~~~

感觉是并查集算法~没学过~~~~~

[此贴子已经被作者于2017-4-21 18:44编辑过]

只有据点个数，没有地域长，宽么？

我有一个想法，不过现在时间不够不能写代码来验证。
首先，读所有坐标的时候把每个点根据x^2+y^2排序建立队列。【根号（x^2+y^2）表示每个点到原点的距离】
然后我们从离原点最近的那个点(x_1,y_1)开始。假设该据点是在某一个驿站的圆上。从队列中找到所有小于x_1^2+y_1^2+（2r）^2的据点，这些点中的一部分一定会和(x_1,y_1)在一个圆中，并且一定会有一个是驿站。{根据找到的据点数目，我们分成两种情况处理：1.没找到据点，则可以判定（x_1,y_1）独立一个驿站；2.找到一个据点，则可以判定这里有个圆以（x_1,y_1）为驿站或者以找到的那个据点为驿站都行，这个驿站能且只能包含这两个据点；3.找到多于1个的据点，那就使用穷举法，分别以每个找到的据点为圆心画圆，看谁收入的据点多就选谁做驿站}
继续从队列中读取一个据点，并重复上一个动作，直到队列为空。
****这个思路算法复杂度优化不太多。只有遇到点阵分布比较离散的时候会快些遇到稠密图那就跟楼主的方法一样累了

据点没有具体的长和宽~只是一个点~

多谢回复~这题现在我先放一放~等抽到时间再来研究一下~

和前面的帖子  没区别的吧？

感觉可以把抽象的数字化简成以下这个问题~

就是在n组数据里面取k组数据~使得k组数据的并查集等于总集，求这个k的最小值~

是有点类似~不过可以知道组合递推最大起点就是选取的数据之间彼此没有连通集的数，然后在这个基础上递推……~~~

[此贴子已经被作者于2017-4-21 22:58编辑过]