Error in solving an OBI problem

Asked

Viewed 50 times

1

I’m trying to solve the problem Wifi of OBI 2018 and I had the idea to create a code that will read and store the coordinates of the rooms and then check if it is "docking" (outside) another room. After that, the code should add 1 for each room that is not internal to another, so I will get the necessary value of wifi’s. However, every time the code is executed, it returns the total number of rooms, causing error. Below is the code:

#include <iostream>
using namespace std;

int main(){
    int N, res = 0;
    typedef struct{
        long int x1, y1, x2, y2;
        int e;
    }sala;
    cin >> N;
    sala v[N];
    for(int i=0;i<N;i++){
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
        v[i].e = 1;
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(v[i].x1 < v[j].x1 && v[i].y1 < v[j].y1 && v[i].x2 > v[j].x2 && v[i].y2 > v[j].y2){
                v[i].e = 0;
                break;
            }
        }
    }
    for(int i=0;i<N;i++){
        res += v[i].e;
    }
    cout << res << endl;
    return 0;
}
c++

1 answer

1


Comparisons are wrong. Replace:

  if(v[i].x1 < v[j].x1 && v[i].y1 < v[j].y1 && v[i].x2 > v[j].x2 && v[i].y2 > v[j].y2){

for: 

 if(v[i].x1 < v[j].x1 && v[i].y1 > v[j].y1 && v[i].x2 > v[j].x2 && v[i].y2 < v[j].y2){

and your algorithm will work.

Well, I tested this algorithm with the fix on the OBI website and the result was 20/100. So, I tried to give an optimized one,but the most I got was an 80/100 rated version. If you’re interested, follow the optimized version:

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

struct Sala {
    int x1;
    int y1;
    int x2;
    int y2; 
};

int main() {

    int N;
    std::cin >> N;
    std::vector<Sala> salas;
    salas.reserve(N);

    int x1, y1, x2, y2;

    for (int i = 0; i < N; i++) {
        std::cin >> x1 >> y1 >> x2 >> y2;
        salas.push_back({ x1, y1, x2, y2 });
    }
    //ordena as salas tomando como parâmetro a posição do lado esquerdo
    //o tempo perdido com a ordenação é mais do que compensado nos loops abaixo
    std::sort(salas.begin(), salas.end(), [](Sala i, Sala j) {return i.x1 < j.x1; });

    int output = N;

    for (int i = 0; i < N; i++) {
        /*o segundo loop é iniciado com j = i, pois como houve a ordenação
        sala[i] nunca estará dentro de sala[j].
        O loop se encerra quando sala[j].x1 for maior ou igual a sala[i].x2, pois as 
        salas que se iniciam depois do lado direito da sala[i] não podem estar dentro de sala[i]
        */
        for (int j = i; j < N && !(salas[j].x1 >= salas[i].x2); j++) {
            if (i == j) { continue; }           
            if (salas[j].x2 < salas[i].x2 && salas[j].y1 < salas[i].y1 && salas[j].y2 > salas[i].y2) {
                output--;
                break;
            }
        }
    }

    std::cout << output;

    return 0;
}

Browser other questions tagged c++

You are not signed in. Login or sign up in order to post.