问题描述
对于平面上的两个点p1=(x1, y1)和p2=(x2,y2)，如果x1<=x2且y1<=y2，则p2支配p1，给定平面上的n个点，请设计算法求其中没有被任何其他点支配的点。
- 换句话说，即：
- 求点集中存在的点，满足：其x、y坐标值不同时小于点集中任意一点的x、y坐标值
思路
-
O
(
n
2
)
O(n^2)
O(n2)算法即：对于每个点分别和其他所有点比较，根据条件判断即可
-
考虑
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)算法
- 任意一个点A，对于所有x坐标大于A的x坐标的点，当且仅当A的y坐标是这些点中最大的y坐标时，点A才是满足题目要求的“没有被其他任何点支配的点”。
- 想要快速的找出所有x坐标大于A的x坐标的点，可以通过排序；以x坐标的关键字、从小到大排序时，数组下标大于A在排序后的数组下标的点就是所要找的点。
- 一般情况下，判断任意一点（假设为排序后第i个）的y坐标是否是i到n中最大的y坐标（或者说该y坐标大于i+1到n中最大的y坐标），复杂度是
O
(
n
2
)
O(n^2)
O(n2)的
-
若倒序找区间最大值，则通过递推可以降低复杂度到
O
(
n
)
O(n)
O(n)
- 这是基于：倒序找最大值时，第i-n个点y坐标最大值，仅与第i个点y坐标、第i+1~n中y坐标最大值有关
完整解法
- 以x坐标值为关键字排序
- 从第n个开始倒序比较，确定对于任意i，i<n，排序后的第i到n点的最大值
- 在比较的过程中，已知第i+1到n点的最大值，若第i点的y坐标大于该最大值，则该点为满足要求的点
- 输出所有满足要求的点
复杂度
- 排序为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)，比较为
O
(
n
)
O(n)
O(n)
代码
struct point{
double x, y;
}a[N];
sort(a+1,a+n+1);
int maxy = a[n];
for (int i=n-1;i>0;i--)
{
if (a[i]>maxy)
{
printf("%d\n", i);
maxy = a[i];
}
}
