The code you write must be in c++ and should not use any external libraries, or “using namespace std”, it can only use #include , but you can not use any built in functions of iostream either
Problem 5
Given is a polygon with n vertices (x1, y1), (x2, y2), . . . , (xn, yn) listed in the clockwise order. Moreover, n is even and the line segments alternate between vertical and horizontal (that is, x2i−1= x2ifor every i∈{1,...,n/2}, and y2i= y2i+1for every i∈{1,...,n/2 − 1}). Additionally, y1= yn= 0, every other y-coordinate is positive (yi> 0 for every y∈{2, . . . , n − 1}), and the x-coordinates form a non-decreasing sequence (that is, x1≤ x2≤ x3≤ ... ≤ xn). Design an O(n) algorithm that finds the largest possible area of an axis- parallel rectangle that fits inside this polygon.
For example, the input on the left is given by vertices (3, 0), (3, 1), (4, 1), (4, 3), (6, 3), (6, 6), (10,6),(10,2),(13,2),(13,5),(17,5),(17,1),(18,1),(18,8),(20,8),(20,0). Therectanglewith the largest area that fits inside this polygon is shown on the right, its area is 26.
Problem 5
Input specification: The first line contains a positive even integer n, indicating the number of vertices of the polygon. Then n lines follow. The i-th line contains two integers, xiand yi. You may assume that all numbers fit within int and that n is at most 1,000,000.
Output specification: The output is a single line with the maximum area of an axis-parallel rectangle that fits inside the polygon.