Header Ads Widget

Chef and the Cake I | Codechef solution

Rajnish Tripathi 04:30

 Your friend Сhef has prepared a rectangular cake for you. Both of you want to divide the cake among yourselves. Your friend is generous enough to let you choose your share first. You have decided to take two pieces.

For the first piece you make a rectangular cut (each side of this cut is parallel to the corresponding side of the cake) inside the cake. Now the cake have two pieces. You take the piece inside the rectangle cut. For the second piece, you make another rectangular cut (each side of this cut is parallel to the corresponding side of the cake) inside the cake. Now the cake again have two pieces. You take the piece inside the rectangle cut (note that this piece may not be rectangular, because of cut may cross an empty space that remains from the first piece, also it can be empty). Your friend will have the rest of the cake.

Given the cuts determine the amount of cake that you will have. The amount is calculated as the sum of the areas covered by your pieces. The cake can be considered as a rectangle with the lower left corner at (0,0) and the upper right corner at (1001,1001).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of two lines. Each line contains the description of a rectangular cut by giving the information of the rectangle. A rectangle is defined by four integers (co-ordinate of the lower-left corner (x1,y1) and upper right corner (x2,y2)).

Output

For each test case, output a single line containing the amount of cake you will have.

Constraints

  • 1≤T≤100
  • 1≤x1<x2≤1000
  • 1≤y1<y2≤1000

Sample 1:

Input
Output
2
1 1 10 10
11 11 20 20
1 1 20 20
11 11 30 30
162
641

Explanation:

Test Case 1: The area of the first piece is 81 and the area of the second piece is 81, a total of 162.

Test Case 2: The area of the first piece is 361 and the area of the second piece is 280, a total of 641.

Code(C++):-

#include <iostream>
using namespace std;


int main() {
    int t;
    cin>>t;
    while(t--)
    {
     int a,b,c,d;
     int A,B,C,D;
     cin>>a>>b>>c>>d;
     cin>>A>>B>>C>>D;
    
     int t= abs(c-a)*abs(d-b) + abs(C-A)*abs(D-B);
int mx1=0,mx2=0,mx3=0,mx4=0;
int ans;
a=max(a,A);
b=max(b,B);
c=min(c,C);
d=min(d,D);
ans=0;
     if(a<c && b<d)
     {
     ans= abs(c-a)*abs(d-b);
     }
     t-=ans;
     cout<<t<<endl;
    }

    return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
         int x1=sc.nextInt()-1;
         int y1=sc.nextInt()-1;
         int x2=sc.nextInt()-1;
         int y2=sc.nextInt()-1;
         int x3=sc.nextInt()-1;
         int y3=sc.nextInt()-1;
         int x4=sc.nextInt()-1;
         int y4=sc.nextInt()-1;
         int arr[][]=new int[1001][1001];
         for(int i=0;i<=1000;i++)
         {
         for(int j=0;j<1001;j++)
         {
         arr[i][j]=1;
         }
         }
         for(int i=x1;i<x2;i++)
         {
         for(int j=y1;j<y2;j++)
         {
         arr[i][j]=0;
         }
         }
         for(int i=x3;i<x4;i++)
         {
         for(int j=y3;j<y4;j++)
         {
         arr[i][j]=0;
         }
         }
         int cnt=0;
         for(int i=0;i<=1000;i++)
         {
         for(int j=0;j<1001;j++)
         {
         if(arr[i][j]==0)
         cnt++;
         }
         }
         System.out.println(cnt);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-




Tags:

Post a Comment

0 Comments