Блог пользователя sidakbhatia

Автор sidakbhatia, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.