Adobe Interview Question for Developer Program Engineers
- 2of 2 votes
AnswersThe King's Land Sale - 2
- sunilkanaujia.manit August 14, 2015 in India
You might have seen shopkeepers offering sale on their trade items to promote their business - like sale on electronic gadgets or sale on clothing and accessories etc. But have you ever come across something like sale of land ?
Yes, the king of Byteland has grown old and wants to sell away his territory as soon as possible. So he announced a sale on his plot. This drew attention of many land lords and everybody hurried to buy land at the cheapest prices. The king had declared that he would accept bids of only rectangular plots and one needs to mention the diagonally opposite corners(a, b) and (c, d) of the land he wishes to buy. They would write these 4 numbers (a, b, c, d) on a piece of paper, seal it in an airtight envelope and give it to the king.
The king received N such envelopes. As the process was hidden there were many envelopes containing plot descriptions that shared some (or even all) common area. The king now wants to know the union of the areas of all plots that have come under the bidding.
Note that the rectangles made by the plots are always aligned to the rectangular axes, their areas is always positive and c >= a and d >= b.
Note that the rectangles made by the plots are always aligned to the rectangular axes, their areas is always positive and c >= a and d >= b.
Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 20
-10000 ≤ a, b, c, d ≤ 10000
Input
The first line of the input contains the number of test cases T. The description of T test cases follow. Each test case starts with a line containing an integer N, the number of rectangular plots. Then N lines follow, each with 4 space separated integers, a b c d,(a, b) and (c, d) representing the diagonally opposite corners of the plots.
Output
For each test case print one line, the union of the areas of all the plots.
Explanation
1) The individual areas of both plots are 4 each. But they share a common area of 1 between them (between (1, 1) and (2, 2)). Therefore the total area is 4 + 4 - 1 = 7
2)Both the plots of no area in common. So we simply add their individual areas (6 + 9 = 15).| Report Duplicate | Flag | PURGE
Adobe Developer Program Engineer Algorithm
Interview Type: Phone Interview