C++：在坐标平面比较坐标的问题中超时不知道怎么解决

Question

最多输入 100,000 个坐标。只应输出对应于特定条件的坐标。如果有比每个坐标x值大和y值小的坐标，则输出列表中排除对应的坐标。

我的英语不好，所以我举一些例子。

[input]先输入要输入的坐标数N。并输入坐标。

[输出]按升序输出条件对应的坐标号

p2 is not correct p4 is correct

[input example]

6
1 3
6 6
7 3
8 2
8 6
2 1

[output example]

4
5
6

限时500ms

[timeout input example]

50000
1 1
1 2
1 3
... skip
1 49999
1 50000

[timeout output example]

1 1
1 2
1 3
... skip
1 49999
1 50000

坐标图像：

下面的问题用一个简单的循环就解决了，但是在输入100000个值的时候出现超时。不知道用什么算法。

我也附上我写的C++源码

另外，我试过使用sort功能，但是当N的个数小的时候，可以正常工作，而当N的个数大的时候，就不能正常比较了。我想我无法正确编写比较函数。所以我尝试在不使用排序的情况下编写源代码。

我想了两天改正了，还是解决不了，求助。感谢阅读。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int N;
    cin >> N;
    bool* visible = new bool[N];
    for (int i = 0; i < N; i++)visible[i] = true;
    
    vector<pair<int,pair<int, int>>> v;
    
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(i,make_pair(a, b)));
    }

    for (int i = 0; i < v.size(); i++) {
        if (visible[i] == false)
            continue;
        for (int j = 0; j < v.size(); j++) {
            if (visible[i] == true &&visible[j]==true && v[i].second.first < v[j].second.first && v[i].second.second > v[j].second.second) {
                visible[i] = false;
                break;
            }
            else if (visible[i] == true && visible[j] == true && v[i].second.first > v[j].second.first && v[i].second.second < v[j].second.second) {
                visible[j] = false;
                continue;
            }
        }
    }
    for (int i = 0; i < v.size(); i++) {
        if (visible[i] == true)
            cout << v[i].first + 1 << endl;
    }
    return 0;
}

[尝试排序失败的源代码]

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
bool* visible;

int compare(pair<int, pair<int, int>> n1, pair<int, pair<int, int>> n2) {
    pair<int, int> a = n1.second, b = n2.second;
    bool swap = false;
    if (a.first > b.first && a.second < b.second) { 
        visible[n2.first - 1] = false;
        swap = true;
    }
    else if (a.first < b.first && a.second > b.second) {
        visible[n1.first - 1] = false;
        //swap = true;
    }

    cout << "[" << n1.first << "]" << a.first << ", " << a.second << " vb : " << visible[n1.first - 1] << " :\t[" << n2.first << "]" << b.first << ", " << b.second << "vb : " << visible[n2.first - 1] << "\t";
    cout << "swap: " << swap << endl;
    return swap;
}
int main() {
    int N;
    cin >> N;
    visible = new bool[N];
    for (int i = 0; i < N; i++)visible[i] = true;
    vector<pair<int, pair<int, int>>> v;

    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(i+1, make_pair(a, b)));
    }
    sort(v.begin(), v.end(), compare);
    for (int i = 0; i < v.size(); i++)
        cout << "p" << v[i].first << " : " << v[i].second.first << ", " << v[i].second.second <<"\t"<< visible[v[i].first-1]<< endl;
    
    return 0;
}

在这种情况下，p4 移动到 (4,2)。在这种情况下，p3,4,5,6 成为正确答案。

Answer 1

我从你的代码中了解到两件事，所以我将列出这两个解决方案：

I：这是修改后的基本示例'Longest Increasing Subsequence'。

让我们首先将坐标视为不同的东西，比方说，坐标 (x,y) 将变成具有高度 (x) 和宽度 (y) 的矩形（将其视为我们正在制作带角的矩形(0,0) (x,0) (0,y) (x,y)).

如果我们需要'ascending'个点，这意味着它们的区域重叠。更正式地说，如果我们需要的点列表是 A(1),A(2),A(3),...,A(k)，那么对于范围 1..k-1 中的每个 i，A( i).x

您可以使用 this

找到最佳解决方案

注意：坐标要排序。依据什么标准？那么只要按照那个条件排序后出现最长的递增子序列就是对的

二：这是一个求凸包的基本例子

多边形的凸包就是凸多边形（节点最多），其坐标集包含在原多边形的坐标集中。我建议阅读 this 。找到上半部分后，你可以应用前面例子中描述的思路，虽然你必须找到一个子串而不是子序列，这样会使复杂度 O(nlog+n)

希望对您有所帮助

Answer 2

给定两个点 A 和 B，存在三种可能的配置：

A让B隐形
B 使 A 隐形
None

点之间的“makes-invisible”关系不是std::sort所要求的strict weak ordering，所以用实现这种关系的比较函数调用std::sort是未定义的。

Answer 3

我不完全确定这对每个极端情况都有效，但想法就在这里。我花了一段时间才确定下来，可能是因为问题描述不是很清楚。基本上你想标记为 不可见 可以找到另一个具有更大 x 和更小 y 的点，即右下角有另一个的点。

如果你在x上对你的点进行排序，那么你只需要检查那些索引较大的点。

事实上，我们只对 y 最小的那个感兴趣，因为它将支配所有其他。

该值只能在从右向左移动时减小，因此我们只需要跟踪最小值 y 即可。唯一的问题是如何处理具有相同 x 的点，因为它们可能在较高的 y 之前具有较低的 y，从而呈现有效点 不可见。诀窍是确保当从右到左浏览时（较高的索引到较低的索引）y 会减小。所以在排序时，如果 x 相等，我们将按 y 排序。

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    struct point {
        int x, y;
        bool visible = true;
    };

    size_t N;
    std::cin >> N;
    std::vector<point> v(N);
    std::vector<size_t> idx(N);
    for (size_t i = 0; i < N; ++i) {
        auto& p = v[i];
        idx[i] = i;
        std::cin >> p.x >> p.y;
    }

    sort(idx.begin(), idx.end(), [&v](const size_t& a, const size_t& b) { 
        if (v[a].x == v[b].x)
            return v[a].y < v[b].y;
        return v[a].x < v[b].x; 
    });

    int miny = INT_MAX;
    for (size_t i = N; i-- > 0;) {
        auto& p = v[idx[i]];
        miny = std::min(miny, p.y);
        if (p.y > miny) {
            p.visible = false;
        }
    }

    for (size_t i = 0; i < N; ++i) {
        auto& p = v[i];
        if (p.visible) {
            std::cout << i + 1 << '\n';
        }
    }

    return 0;
}

C++：在坐标平面比较坐标的问题中超时不知道怎么解决

C++: I don't know how to solve the timeout in the problem of comparing coordinates in the coordinate plane

c++

algorithm

coordinates