use*_*960 9 algorithm geometry
找出下一个问题的算法:给定2D平面中n个点的集合S,如果x1> x2且y1> y2,则点(x1,y1)支配另一个点(x2,y2).找到最大的点集M,使得M是S的子集,并且没有M的点由S的另一个点支配.
int*_*jay 8
通过增加x坐标对所有点进行排序.如果两个点具有相同的x坐标,则通过减小y坐标对它们进行排序.现在,可以看出点的子集是不可支配当且仅当他们的y坐标是在我们的排序顺序不增加,这意味着每个y坐标小于或等于前一个子序列.
所以算法将是:
这给出了O(n*logn)中可能的最大集合.
归档时间：
12 年，8 月 前
查看次数：
2966 次
最近记录：
6 年，6 月 前