给定二维平面整数点集输出“最大点集”算法（今日头条面试题）

#include
#include
#include
#include 
#include using namespace std;
struct point{     //定义结构体
    int x,y;
};
bool cmp(point a,point b){  //自定义排序方法
    return a.y==b.y?a.x>b.x:a.y//y升序，x降序
}
int main(){
    clock_t start,finish;
    double totaltime;
    std::srand(std::time(nullptr)); // use current time as seed for random generator
    int count;  
    cout"输入点的个数和点：" ;
    cin>>count;
    vector p; //容器用来装平面上的点
    for(int i=0;i){
        point temp;
        temp.x = std::rand()% 100000000;
        temp.y = std::rand()% 100000000;
        p.push_back(temp); //为了方便对比性能，我们随机插入大量点
    }
    start = clock();
    vector filter;//定义过滤容器
    vector res;  //定义结果容器
    int curMaxRank = 0;
    int curMaxIndex = 0;
    for(int i=0;i){
        int temp =p[i].x+p[i].y-std::abs(p[i].x-p[i].y);
        if(temp > curMaxRank)
        {
            curMaxRank = temp;
            curMaxIndex = i;
        }
    }
    for(int i=0;i)
    {
        if(p[i].x >= p[curMaxIndex].x || p[i].y>= p[curMaxIndex].y)
        {
            filter.push_back(p[i]);
        }
    }
    
    sort(filter.begin(),filter.end(),cmp);
    res.push_back(filter[filter.size()-1]);  //左上角的那个点，一定符合条件
    int maxx=filter[filter.size()-1].x;
    for(int i=filter.size()-2;i>=0;i--){  //y从大到小，若i点x值大于所有比其y值大的点的x值，那么i点为“最大点”。
        if(filter[i].x>maxx){
            res.push_back(filter[i]);
            maxx=filter[i].x;
        }
    }
    finish = clock();
    cout"过滤后点数量："endl;
    cout"符合条件的点数量："endl;
    for(int i=0;i){
        printf("%d %d\n", res[i].x, res[i].y);
    }
    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
    cout"\n此程序的运行时间为""秒！"endl;
    cout"------------------------------------------------"endl;
    start = clock();
    sort(p.begin(),p.end(),cmp); 
    res.clear();
    res.push_back(p[p.size()-1]);  //左上角的那个点，一定符合条件
    int maxX=p[p.size()-1].x;
    for(int i=p.size()-2;i>=0;i--){  
        //y从大到小，若i点x值大于所有比其y值大的点的x值，那么i点为“最大点”。
        if(p[i].x>maxX){
            res.push_back(p[i]);
            maxX=p[i].x;
        }
    }
    finish = clock();
    cout"符合条件的点数量："endl;
    for(int i=0;i){
        printf("%d %d\n", res[i].x, res[i].y);
    }
    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
    cout"\n此程序的运行时间为""秒！"endl;
    
    return 0;
}