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

Question

Up to 100,000 coordinates are entered. Only coordinates corresponding to specific conditions should be output. If there are coordinates with larger x values ​​and smaller y values ​​than each coordinate, the corresponding coordinates are excluded from the output list.

My English is not good, so I'm giving some examples.

[input] First enter the number of coordinates N to be input. and enter the coordinates.

[output] The coordinate numbers corresponding to the condition are output in ascending order.

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

The time limit is 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

coordinates image:

The following problem was solved with a simple loop, but a timeout occurs when 100,000 values ​​are entered. I don't know which algorithm to use.

I also attach the C++ source code I wrote.

Also, I tried using the sort function, but when the number of N is small, it works fine, and when the number of N is large, it cannot be compared properly. I guess I couldn't write the compare function properly. So I tried writing the source code without using sort.

I thought and corrected it over two days, but I couldn't solve it, so I seek help. thanks for reading.

#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;
}

[Source code that tried to sort but failed]

#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;
}

In this case, p4 moves to (4,2). In this case, p3,4,5,6 becomes the correct answer.

Answer 1

I'm not totally sure this works for every corner case, but the idea is here. It took me a while to nail it down, probably because the problem description wasn't exactly clear. Basically you want to mark as not visible the points for which it is possible to find another one with a larger x and a smaller y, i.e. the points which have another on their lower right.

If you sort your points on x, then you only need to check those with a larger index.

In fact, we are interested only in the one with the minimum y, because it will dominate all others.

That value can only decrease while moving from right to left, so we just need to keep track of the minimum y. The only problem is how to deal with points that have the same x, because they could have a lower y before a higher one, rendering valid points non visible. The trick is to make sure that when browsed from right to left (higher indices to lower ones) the y will decrease. So when sorting, if x is equal we will sort on 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;
}

Answer 2

I understood two things from your code, so I'll list both the solutions:

I: This is a basic example of a modified 'Longest Increasing Subsequence'.

Let's first consider the coordinates as something different, let's say , the coordinate (x,y), would become the ractangle with height (x) and width (y) (consider this as if we were making rectangles with corners (0,0) (x,0) (0,y) (x,y)).

If we need 'ascending' points, it means that their areas overlap. More formally, if the list of point we need is A(1),A(2),A(3),...,A(k), then for each i in range 1..k-1, A(i).x<A(i+1).x and A(i).y<A(i+1).y.

You can find an optimal solution using this

Note: the coordinates should be sorted. By what criteria? Well, as long as the longest increasing subsequence would appear after a sorting of that criteria, then it's correct.

II: This is a basic example of finding the convex hull.

The convex hull of a polygon would be the convex polygon (with the most nodes) , whose set of coordinates is included in the set of the coordinates of the original polygon. I recommend reading this . After finding the upper half, you can apply a mentality as described in the previous example, although you must find a substring instead of a subsequence, so that would make the complexity O(nlog+n)

Hope this was helpful

Answer 3

Given two points A and B, there are three possible configurations:

1. A makes B invisible
2. B makes A invisible
3. None of the above

The "makes-invisible" relation between the points is not strict weak ordering required by std::sort, so calling std::sort with a comparison function that implements this relation is undefined.