Minimum Bounding Rectangle

[abhi_bansal]

I am currently solving a problem linked https://www.spoj.com/problems/HS12MBR but don’t know why i am getting 0 points.It’s working fine on my IDE.Can you help me in what can i do to make the code better to make it run on spoj??

#include<iostream>

using namespace std;
int main() {
  int t, n;
  char type;
  int x1, x2, y1, y2, r;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> n;
    for (int j = 0; j < n; j++) {
      cin >> type;
      if (type == 'p') {
        cin >> x1 >> y1;
        cout << x1 << y1 << x1 << y1 << "\n";
      } else if (type == 'l') {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << x1 << y1 << x2 << y2 << "\n";
      } else {
        cin >> x1 >> y1 >> r;
        cout << x1 - r << y1 - r << x1 + r << y1 + r << "\n";
      }
    }
  }
  return 0;
}

Thank you

[simes]

I think you’re supposed to find the bounding rectangle for all objects in the set, not for each object individually.

Run it with the sample data and ensure you give exactly the same output.

[abhi_bansal]

Thanks for your reply.
I ran it again and the output is exactly what it wants.If time persists you can check my code…

[simes]

No it isn’t

I gave your code the sample input from the problem statement, and this is what it produced:

3333
-10-103030
10103030
0010020

The expected output is this:

3 3 3 3
-10 -10 30 30
0 0 100 20

Can you see any differences now?

[abhi_bansal]

Actually the output given in the question is wrong because my solution did got accepted. I was just referring to the points.I have added the proof.
Also if you see the question there are 2 circles as input but the output is corresponding to 1 circle only.This is where the mistake is .

[simes]

Sorry, but you’re mistaken. Take a look at the status page, and see how many points you got. It’s 0, meaning you got all test cases wrong.

The sample output is correct. There are three lines of output because there are three sets of input. As you’ve noticed, the second set contains two circles. You need to calculate a single bounding rectangle that surrounds all objects in each set.

That’s what I did:

[abhi_bansal]

Yeah you are right.I actually misunderstood the problem. I have changed the code accordingly
Now i am at 40 points.Just wanted to ask whether in the mixed combination of point and circle will i need to consider tangents. If possible can you give me some examples on cases because its not given in the problem.
Thanks

[simes]

I’m guessing that 40 points means you’re getting points and circles correct, so take a closer look at lines.

Don’t assume x1,y1 is to the left and below x2,y2.

[abhi_bansal]

No I’ m not taking x1,y1 to the left thing.just wanted to ask suppose we have L1= (1,10),(2,9),
L2=(3,8),(4,7).
Now MBR can be thin rectangle of tending to 0 area connecting (1,10) and (4,7) or am i missing something??.

Here 's the code.

#include<iostream>
using namespace std;
int main()
{
    int t,n;char type;
    cin>>t;
    int x1,x2,y1,y2,r,lx{1000},ly{1000},rx{-1000},ry{-1000};
    for(int j=0;j<t;j++)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
          cin>>type;
            if(type=='l')
            {
                cin>>x1>>y1>>x2>>y2;
                if(x1>rx)    rx=x1;
                if(x2>rx)    rx=x2;
                
                if(x1<lx)   lx=x1;
                if(x2<lx)   lx=x2;
                
                if(y1>ry)   ry=y1;
                if(y2>ry)   ry=y2;
                
                if(y1<ly)   ly=y1;
                if(y2<ly)   ly=y2;
            }  
            
            else if(type=='c')
            {
                cin>>x1>>y1>>r;
                if(x1+r>rx) rx=x1+r;
                
                if(y1+r>ry) ry=y1+r;
                
                if(x1-r<lx) lx=x1-r;
                
                if(y1-r<ly) ly=y1-r;
            }
            
            else 
            {
                cin>>x1>>y1;
                if(x1>rx)   rx=x1;
                
                if(x1<lx)   lx=x1;
                
                if(y1>ry)   ry=y1;
                
                if(y1<ly)   ly=y1;
        }
    }
    cout<<lx<<" "<<ly<<" "<<rx<<" "<<ry<<"\n";
    lx=1000;ly=1000;rx=0;ry=0;
    }    
    return 0;
}

Thank You

[simes]

The problem statement says the MBR must be axis-aligned, so no.

Take another look at this line.

lx=1000;ly=1000;rx=0;ry=0;

[abhi_bansal]

Thanks for your time .Finally got 100 points.
The lower bound of rx and ry should be -1000.