1

Here is the question below:

Farmer John has decided to update his farm to simplify its geometry. Previously, his cows grazed in two rectangular fenced-in pastures. Farmer John would like to replace these with a single square fenced-in pasture of minimum size that still covers all the regions of his farm that were previously enclosed by the former two fences. Please help Farmer John figure out the minimum area he needs to make his new square pasture so that if he places it appropriately, it can still cover all the area formerly covered by the two older rectangular pastures. The square pasture should have its sides parallel to the x and y axes.

INPUT FORMAT (file square.in): The first line in the input file specifies one of the original rectangular pastures with four space-separated integers x1 y1 x2 y2, each in the range 0…10. The lower-left corner of the pasture is at the point (x1,y1), and the upper-right corner is at the point (x2,y2), where x2>x1 and y2>y1. The second line of input has the same 4-integer format as the first line, and specifies the second original rectangular pasture. This pasture will not overlap or touch the first pasture.

OUTPUT FORMAT (file square.out): The output should consist of one line containing the minimum area required of a square pasture that would cover all the regions originally enclosed by the two rectangular pastures.

SAMPLE INPUT:

6 6 8 8

1 8 4 9

SAMPLE OUTPUT:

49

And below is my solution:

#include<bits/stdc++.h>

using namespace std;

int main(){
int rect1[4], rect2[4], N[2];

for (int i=0;i<4;i++){
    cin >> rect1[i];
}
for (int i=0;i<4;i++){
    cin >> rect2[i];
}

if (abs(rect1[0] - rect2[2]) >= abs(rect1[2] - rect2[0])){
    N[0] = abs(rect1[0] - rect2[2]);
}else{
    N[0] = abs(rect1[2] - rect2[0]);
}

if (abs(rect1[1] - rect2[3]) >= abs(rect1[3] - rect2[1])){
    N[1] = abs(rect1[1] - rect2[3]);
}else{
    N[1] = abs(rect1[3] - rect2[1]);
}

if (N[0] >= N[1]){
    cout << pow(N[0], 2);
}else{
    cout << pow(N[1], 2);
}}

I used the array N[0] to record the width, and N[1] to record the height. Then, I squared the bigger of the two to get the answer.

When I submitted this, it kept saying it was wrong, but it doesn't show me why... Please help me...

And please forgive me if I am seen as an "amateur," I started coding a week ago, and this is my first time using stack overflow..!

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
Hide_on_bush
  • 11
  • 2
  • 3
    It would be better to learn C++ using a [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) instead of by solving random online puzzles. These books are also available as PDFs for free. – Jason Oct 11 '22 at 14:58
  • 3
    I agree with Jason Liam. C++ is full of "what you don't know CAN hurt you" - it's really, really easy to pick up "bad habits". For example: [Why You Should Avoid Using #include While Writing Code](https://hackernoon.com/why-you-should-avoid-using-include-lessbitsstdchgreater-while-writing-code-8y2035va) – paulsm4 Oct 11 '22 at 15:00
  • If you rotate a square by 45°, then it would still be a square. It doesn't have to be aligned with the x and y axis – Lanting Oct 11 '22 at 15:01
  • @Lanting but it will fail to have its sides parallel to x and y axes (as required). – Öö Tiib Oct 11 '22 at 15:10
  • It is because your program happens to give correct answer only to limited input data. – Öö Tiib Oct 11 '22 at 15:18
  • `pow` operates on floating point numbers and floating point computations are not always precise. The lack of precision is especially painful when you are working on integers and the result was a close-enough-for-floating-point 24.9999999997which will be truncated to the integer value 24. – user4581301 Oct 11 '22 at 15:23
  • Also worth noting that `pow` needs to handle the really tough stuff like computing e to the power of pi, so using it to simply square a number can be vast overkill. Modern compilers tend to be smart and can see what you're doing and can replace `pow(N[0], 2)` with a much faster `N[0]*N[0]`. But if it can't, you may be better off being explicit. – user4581301 Oct 11 '22 at 15:28

1 Answers1

1

I can understand your reasoning, but there are cases when it will not work. Think about the case when pasture1 totally encompasses pasture2. In such a case, your solution will not work.

A possible objection to my statement above is to quote from the assignment specification

This pasture will not overlap or touch the first pasture.

which is true. But notice what the assinment didn't say: it did not say that the x1 and x2 of the second rectangle cannot be between the x1 and x2 of the second rectangle. Let me provide you an example when the specification is not violated, but this problem occurs:

rectangle1:

  • x1: 0
  • y1: 0
  • x2: 10
  • y2: 1

rectangle2:

  • x1: 1
  • y1: 2
  • x2: 9
  • y2: 3

do they overlap? No, of course not. What will your program compute as the necessary width:

|0 - 9| >= |1 - 10| (they are both 9). So, the necessary width that you compute is 9. But the real necessary width is 10, because x1 and x2 of the first rectangle are between x1 and x2 of the second rectangle and the situation still does not violate the specification because the differences in y1 and y2 values ensure that the specification is correct.

So, instead of assuming that none of the rectangle encompasses the other one given a single dimension (without overlapping), we need to compute the minimum of x1 values of the two rectangles and the maximum value of the x2 values of the two rectangles and compute the difference. That will be the necessary with.

The same reasoning stands for height and y values and I'm too lazy to write it down again :)

I will not write the code for you to avoid ruining the fun of learning, but this is the algorithm:

  • width = max(rect1[2], rect2[2]) - min(rect1[0], rect2[0])
  • height = max(rect1[3], rect2[3]) - min(rect1[1], rect2[1])

Have fun implementing it and testing it!

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175