现在二维坐标系里面有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编辑过]

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

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

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

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

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

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

最新进展就是除了去除真子集外还可以进行优先级遍历~先选出现数字次数比较小的~这样剪枝速度会快一些~

看了一下~暂时没有一种能直接得出结果的方法~这有点类似组合密码锁问题~就是在一堆密钥中选取若干段密钥来恰好能组合出一个完整的密码~~除了剪枝外只能进行深度或者广度搜索了~~~