sidakbhatia's blog

Help Needed in coding Problem
By sidakbhatia, history, 3 years ago, In English

Hey I was recently giving a coding test for a company and this question appeared.

You are given points (0,0) (N,0) (0,M) and (N,M) that form a rectangle. You have a point (x,y) that is within a rectangle or on one of its edges. Now a straight line is drawn passing through (x,y) to cut the rectangle into 2 parts. Find the max possible area of the part whose area is not larger than the other. Also determine if there are multiple ways to cut the rectangle and achieve the maximum.

Input: N M X Y

1<= N,M<= 1E9

0<=X<=N

0<=Y<=M

Output: Print the max possible area followed by 1 if there are multiple ways to cut the rectangle and achieve maximum else print 0

Sample cases:

2 3 1 2

3.00000 0

the line x=1 gives the optimal cut with no other posibilties.

2 4 1 2

4.000000 1

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sidakbhatia (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

The answer for area is always half of the area of rectangle(correct me if I am wrong). And multiple answers are only possible if that point is at the centre of the rectangle.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This did cross my mind after the contest. Any formal proof for the assertion that given a a point we can always draw a line through it cutting the rectangle in half.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well you can draw a line passing from the given point and centre of the rectangle and you can see that this line split the given rectangle into two equal parts.

      → Reply