Given a rectangle [(x1, y1), (x2, y2)] denoting the coordinates of bottom-left corner and top-right corner whose sides are parallel to coordinates axes and N points on its perimeter (at least one on each side). The task is to maximize the area of a triangle formed by these points.
Examples:
Input: rectangle[][]= {{0, 0}, {6, 6}},
coordinates[][] = {{0, 2}, {0, 3}, {0, 5}, {2, 0}, {3, 0}, {6, 0}, {6, 4}, {1, 6}, {6, 6}}
Output: 18
Explanation: Refer to the image below for explanation.
Approach: For finding the maximum area triangle by coordinates on a given rectangle, find the coordinates on each side which are most distant apart. So, suppose there are four sides a, b, c, d where a and c being the length of the rectangle and b, d being the breadth. Now the maximum area will be
MAX ( length * ( distance between farthest coordinates on either of breadth) / 2, breadth * ( distance between farthest coordinates on either of length) / 2 ).
Follow the steps below to solve the given problem.
- Calculate the length = abs(x2 – x1) and breadth = abs(y2 – y1)
- Find the coordinates which are farthest from each other on each side.
- Use the above-mentioned formula to calculate the area.
- Return the area found.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>#include <iostream>using namespace std;// To find the maximum area of trianglevoid maxTriangleArea(int rectangle[2][2], int coordinates[][2], int numberOfCoordinates){ int l1min = INT_MAX, l2min = INT_MAX, l1max = INT_MIN, l2max = INT_MIN, b1min = INT_MAX, b1max = INT_MIN, b2min = INT_MAX, b2max = INT_MIN; int l1Ycoordinate = rectangle[0][1]; int l2Ycoordinate = rectangle[1][1]; int b1Xcoordinate = rectangle[0][0]; int b2Xcoordinate = rectangle[1][0]; // Always consider side parallel // to x-axis as length and // side parallel to y-axis as breadth for (int i = 0; i < numberOfCoordinates; i++) { coordinates[i][1]; // coordinate on l1 if (coordinates[i][1] == l1Ycoordinate) { l1min = min(l1min, coordinates[i][0]); l1max = max(l1max, coordinates[i][0]); } // Coordinate on l2 if (coordinates[i][1] == l2Ycoordinate) { l2min = min(l2min, coordinates[i][0]); l2max = max(l2max, coordinates[i][0]); } // Coordinate on b1 if (coordinates[i][0] == b1Xcoordinate) { b1min = min(b1min, coordinates[i][1]); b1max = max(b1max, coordinates[i][1]); } // Coordinate on b2 if (coordinates[i][0] == b2Xcoordinate) { b2min = min(b2min, coordinates[i][1]); b2max = max(b2max, coordinates[i][1]); } } // Find maximum possible distance // on length int maxOfLength = max(abs(l1max - l1min), abs(l2max - l2min)); // Find maximum possible distance // on breadth int maxofBreadth = max(abs(b1max - b1min), abs(b2max - b2min)); // Calculate result base * height / 2 float result = max((maxofBreadth * (abs(rectangle[0][0] - rectangle[1][0]))), (maxOfLength * (abs(rectangle[0][1] - rectangle[1][1])))) / 2.0; // Print the result cout << result;}// Driver Codeint main(){ // Rectangle with x1, y1 and x2, y2 int rectangle[2][2] = { { 0, 0 }, { 6, 6 } }; // Coordinates on sides of given rectangle int coordinates[9][2] = { { 0, 2 }, { 0, 3 }, { 0, 5 }, { 2, 0 }, { 3, 0 }, { 6, 0 }, { 6, 4 }, { 1, 6 }, { 6, 6 } }; int numberOfCoordinates = sizeof(coordinates) / sizeof(coordinates[0]); maxTriangleArea(rectangle, coordinates, numberOfCoordinates); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // To find the maximum area of triangle static void maxTriangleArea(int[ ][ ] rectangle, int[ ][ ] coordinates, int numberOfCoordinates) { int l1min = Integer.MAX_VALUE, l2min = Integer.MAX_VALUE, l1max = Integer.MIN_VALUE, l2max = Integer.MIN_VALUE, b1min = Integer.MAX_VALUE, b1max = Integer.MIN_VALUE, b2min = Integer.MAX_VALUE, b2max = Integer.MIN_VALUE; int l1Ycoordinate = rectangle[0][1]; int l2Ycoordinate = rectangle[1][1]; int b1Xcoordinate = rectangle[0][0]; int b2Xcoordinate = rectangle[1][0]; // Always consider side parallel // to x-axis as length and // side parallel to y-axis as breadth for (int i = 0; i < numberOfCoordinates; i++) { // coordinate on l1 if (coordinates[i][1] == l1Ycoordinate) { l1min = Math.min(l1min, coordinates[i][0]); l1max = Math.max(l1max, coordinates[i][0]); } // Coordinate on l2 if (coordinates[i][1] == l2Ycoordinate) { l2min = Math.min(l2min, coordinates[i][0]); l2max = Math.max(l2max, coordinates[i][0]); } // Coordinate on b1 if (coordinates[i][0] == b1Xcoordinate) { b1min = Math.min(b1min, coordinates[i][1]); b1max = Math.max(b1max, coordinates[i][1]); } // Coordinate on b2 if (coordinates[i][0] == b2Xcoordinate) { b2min = Math.min(b2min, coordinates[i][1]); b2max = Math.max(b2max, coordinates[i][1]); } } // Find maximum possible distance // on length int maxOfLength = Math.max(Math.abs(l1max - l1min), Math.abs(l2max - l2min)); // Find maximum possible distance // on breadth int maxofBreadth = Math.max(Math.abs(b1max - b1min), Math.abs(b2max - b2min)); // Calculate result base * height / 2 int result = Math.max((maxofBreadth * (Math.abs(rectangle[0][0] - rectangle[1][0]))), (maxOfLength * (Math.abs(rectangle[0][1] - rectangle[1][1])))) / 2; // Print the result System.out.print(result); } // Driver Code public static void main (String[] args) { // Rectangle with x1, y1 and x2, y2 int[ ][ ] rectangle = { { 0, 0 }, { 6, 6 } }; // Coordinates on sides of given rectangle int[ ][ ] coordinates = { { 0, 2 }, { 0, 3 }, { 0, 5 }, { 2, 0 }, { 3, 0 }, { 6, 0 }, { 6, 4 }, { 1, 6 }, { 6, 6 } }; int numberOfCoordinates = coordinates.length; maxTriangleArea(rectangle, coordinates, numberOfCoordinates); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach # To find the maximum area of triangledef maxTriangleArea(rectangle, coordinates, numberOfCoordinates): l1min = 10 ** 9 l2min = 10 ** 9 l1max = 10 ** -9 l2max = 10 ** -9 b1min = 10 ** 9 b1max = 10 ** -9 b2min = 10 ** 9 b2max = 10 ** -9 l1Ycoordinate = rectangle[0][1]; l2Ycoordinate = rectangle[1][1]; b1Xcoordinate = rectangle[0][0]; b2Xcoordinate = rectangle[1][0]; # Always consider side parallel # to x-axis as length and # side parallel to y-axis as breadth for i in range(numberOfCoordinates): coordinates[i][1]; # coordinate on l1 if (coordinates[i][1] == l1Ycoordinate) : l1min = min(l1min, coordinates[i][0]); l1max = max(l1max, coordinates[i][0]); # Coordinate on l2 if (coordinates[i][1] == l2Ycoordinate): l2min = min(l2min, coordinates[i][0]); l2max = max(l2max, coordinates[i][0]); # Coordinate on b1 if (coordinates[i][0] == b1Xcoordinate): b1min = min(b1min, coordinates[i][1]); b1max = max(b1max, coordinates[i][1]); # Coordinate on b2 if (coordinates[i][0] == b2Xcoordinate): b2min = min(b2min, coordinates[i][1]); b2max = max(b2max, coordinates[i][1]); # Find maximum possible distance # on length maxOfLength = max(abs(l1max - l1min), abs(l2max - l2min)); # Find maximum possible distance # on breadth maxofBreadth = max(abs(b1max - b1min), abs(b2max - b2min)); # Calculate result base * height / 2 result = max((maxofBreadth * (abs(rectangle[0][0] - rectangle[1][0]))), (maxOfLength * (abs(rectangle[0][1] - rectangle[1][1])))) / 2.0; # Print the result print(int(result));# Driver Code# Rectangle with x1, y1 and x2, y2rectangle = [[0, 0],[6, 6]];# Coordinates on sides of given rectanglecoordinates = [[0, 2], [0, 3], [0, 5], [2, 0], [3, 0], [6, 0], [6, 4], [1, 6], [6, 6]];numberOfCoordinates = len(coordinates)maxTriangleArea(rectangle, coordinates, numberOfCoordinates);# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG { // To find the maximum area of triangle static void maxTriangleArea(int[,] rectangle, int[,] coordinates, int numberOfCoordinates) { int l1min = Int32.MaxValue, l2min = Int32.MaxValue, l1max = Int32.MinValue, l2max = Int32.MinValue, b1min = Int32.MaxValue, b1max = Int32.MinValue, b2min = Int32.MaxValue, b2max = Int32.MinValue; int l1Ycoordinate = rectangle[0,1]; int l2Ycoordinate = rectangle[1,1]; int b1Xcoordinate = rectangle[0,0]; int b2Xcoordinate = rectangle[1,0]; // Always consider side parallel // to x-axis as length and // side parallel to y-axis as breadth for (int i = 0; i < numberOfCoordinates; i++) { // coordinate on l1 if (coordinates[i,1] == l1Ycoordinate) { l1min = Math.Min(l1min, coordinates[i,0]); l1max = Math.Max(l1max, coordinates[i,0]); } // Coordinate on l2 if (coordinates[i,1] == l2Ycoordinate) { l2min = Math.Min(l2min, coordinates[i,0]); l2max = Math.Max(l2max, coordinates[i,0]); } // Coordinate on b1 if (coordinates[i,0] == b1Xcoordinate) { b1min = Math.Min(b1min, coordinates[i,1]); b1max = Math.Max(b1max, coordinates[i,1]); } // Coordinate on b2 if (coordinates[i,0] == b2Xcoordinate) { b2min = Math.Min(b2min, coordinates[i,1]); b2max = Math.Max(b2max, coordinates[i,1]); } } // Find maximum possible distance // on length int maxOfLength = Math.Max(Math.Abs(l1max - l1min), Math.Abs(l2max - l2min)); // Find maximum possible distance // on breadth int maxofBreadth = Math.Max(Math.Abs(b1max - b1min), Math.Abs(b2max - b2min)); // Calculate result base * height / 2 int result = Math.Max((maxofBreadth * (Math.Abs(rectangle[0,0] - rectangle[1,0]))), (maxOfLength * (Math.Abs(rectangle[0,1] - rectangle[1,1])))) / 2; // Print the result Console.Write(result); } // Driver Code public static void Main () { // Rectangle with x1, y1 and x2, y2 int[,] rectangle = { { 0, 0 }, { 6, 6 } }; // Coordinates on sides of given rectangle int[,] coordinates = { { 0, 2 }, { 0, 3 }, { 0, 5 }, { 2, 0 }, { 3, 0 }, { 6, 0 }, { 6, 4 }, { 1, 6 }, { 6, 6 } }; int numberOfCoordinates = coordinates.GetLength(0); maxTriangleArea(rectangle, coordinates, numberOfCoordinates); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // To find the maximum area of triangle function maxTriangleArea(rectangle, coordinates, numberOfCoordinates) { let l1min = Number.MAX_VALUE, l2min = Number.MAX_VALUE, l1max = Number.MIN_VALUE, l2max = Number.MIN_VALUE, b1min = Number.MAX_VALUE, b1max = Number.MIN_VALUE, b2min = Number.MAX_VALUE, b2max = Number.MIN_VALUE; let l1Ycoordinate = rectangle[0][1]; let l2Ycoordinate = rectangle[1][1]; let b1Xcoordinate = rectangle[0][0]; let b2Xcoordinate = rectangle[1][0]; // Always consider side parallel // to x-axis as length and // side parallel to y-axis as breadth for (let i = 0; i < numberOfCoordinates; i++) { coordinates[i][1]; // coordinate on l1 if (coordinates[i][1] == l1Ycoordinate) { l1min = Math.min(l1min, coordinates[i][0]); l1max = Math.max(l1max, coordinates[i][0]); } // Coordinate on l2 if (coordinates[i][1] == l2Ycoordinate) { l2min = Math.min(l2min, coordinates[i][0]); l2max = Math.max(l2max, coordinates[i][0]); } // Coordinate on b1 if (coordinates[i][0] == b1Xcoordinate) { b1min = Math.min(b1min, coordinates[i][1]); b1max = Math.max(b1max, coordinates[i][1]); } // Coordinate on b2 if (coordinates[i][0] == b2Xcoordinate) { b2min = Math.min(b2min, coordinates[i][1]); b2max = Math.max(b2max, coordinates[i][1]); } } // Find maximum possible distance // on length let maxOfLength = Math.max(Math.abs(l1max - l1min), Math.abs(l2max - l2min)); // Find maximum possible distance // on breadth let maxofBreadth = Math.max(Math.abs(b1max - b1min), Math.abs(b2max - b2min)); // Calculate result base * height / 2 let result = Math.max((maxofBreadth * (Math.abs(rectangle[0][0] - rectangle[1][0]))), (maxOfLength * (Math.abs(rectangle[0][1] - rectangle[1][1])))) / 2.0; // Print the result document.write(result); } // Driver Code // Rectangle with x1, y1 and x2, y2 let rectangle = [[0, 0], [6, 6]]; // Coordinates on sides of given rectangle let coordinates = [[0, 2], [0, 3], [0, 5], [2, 0], [3, 0], [6, 0], [6, 4], [1, 6], [6, 6]]; let numberOfCoordinates = coordinates.length; maxTriangleArea(rectangle, coordinates, numberOfCoordinates); // This code is contributed by Potta Lokesh </script> |
Output
18
Time complexity: O(N), Where N is the number of coordinates given.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
