CODEWITHSUNDEEP
algorithmgeometryarea
hmims
hmims

Reputation: 539

Maximum area of triangle having all vertices of different color

Points from (0,0) to (R,C) in the cartesian plane are colored r, g or b. Make a triangle using these points such that-

a) All three vertices are of different colors.
b) At least one side of triangle is parallel to either of the axes.
c) Area of the triangle is maximum possible.

Output the maximum possible area. Constraints : 1<=R<=1000 , 1<=C<=1000

Can someone please let me know the approach to this question?

Upvotes: 0

Views: 2031

Answers (1)

user3386109
user3386109

Reputation: 34829

The area of a triangle is 1/2 * base * height. So if one side of the triangle is parallel to the
x-axis, then the base of the triangle is formed by two colors on the same row (spread as far apart as possible), and the third color should be on the row that's farthest from the base. Hence, you can preprocess the data to find:

  1. the top-most and bottom-most row for each color
  2. the left-most and right-most column for each color on every row

Then for every row, you have twelve possibilities for forming a triangle, e.g. 

left-most-red, right-most-blue, top-most green
left-most-red, right-most-blue, bottom-most green
left-most-red, right-most-green, top-most blue
...

And of course, there's the corresponding process for triangles with one edge parallel to the y-axis.

Thus, the problem can be solved in O(R*C) time, where most of the time is spent in the preprocessing.

Upvotes: 2

Related Questions