Not able to understand the question

#1

Can you explain the question I don’t really get it

#2

@bhavik911,

Clearly the maximum area would be between the intersection points of (2,4) and (5,2) for the given sample testcase.

Area = | 5 - 2 - 1 | * | 2 - 4 - 1| = 2 * 1 = 2

We implement the formula ,
Area = abs( y2 - y1 - 1) * abs( x2 - x1 - 1)//take abs as area cant be negative

We add an extra -1 in our calculation since we should consider the river area. If we simply implement (y2 - y1) or (x2 - x1) then we would end up counting 1 edge of the vertical river and 1 edge of the horizontal river. We should not include that area as the temple cannot be built over the river edge.

You can refer to the image below.

WhatsApp Image 2020-05-03 at 10.27.25
WhatsApp Image 2020-05-03 at 10.27.25870×1160 88.6 KB

#3 
package Arrays;

import javafx.scene.transform.Scale;

import java.util.Arrays;
import java.util.Scanner;

public class GrandTemple {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] arr = new int[2][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                arr[j][i] = scanner.nextInt();
            }
        }
        for (int i = 0; i < 2; i++) {
         Arrays.sort(arr[i]);
        }

        int max = 0;
        int curr =0;
        for(int i =0;i<n-1;i++){
            int x1= arr[0][i];
            int x2 =arr[0][i+1];
            int y1= arr[1][i];
            int y2 =arr[1][i+1];
            curr = Math.abs(x2-x1-1)*Math.abs(y2-y1-1);
            if(curr>max){
                max = curr;
            }
        }
        System.out.println(max);
    }
}

This is my code , but it is showing wrong test case what might be the problem here?

#4

Did you see it , please review

#5

@bhavik911,
Take 2 1D arrays for input. One for X and one for Y instead of a 2D array. Sort them individually and then follow the same approach. The order of points might change but that won’t make a difference because, we need to find the max area possible

#6

So the points should not be one after other?
I mean if they are not consecutive there might be a river between them
Also what is the error is my approach?

#7

@bhavik911,
I am sorry I made an error in jugdement in my last post.

https://ide.codingblocks.com/s/294759 corrected code.

Error:
You have to find the max difference between points on both the axis first and then the area.
Now, what you are doing was finding the max area between consecutive points.

Correct approach:

diff_in_x = Math.max(diff_in_x, Math.abs(x2 - x1) - 1);
diff_in_y = Math.max(diff_in_y, Math.abs(y2 - y1) - 1);

And then just print the product of diff_in_x and diff_in_y

#8

But in this case the x and y will not correspond to each other right?
What if there comes a river in between then

#9

@bhavik911,
If you think make a graph and start plotting points you will observe, we will have that test case covered as well :slight_smile:

1 Like