Python Code for Polygon TCS Codevita
Coding Question 4
In this article, we will discuss about the TCS CodeVita Coding Question which is asked in the TCS placement test along with a detailed solution. This will help you excel your coding problems.
Polygon Coding Question
Problem Description:
You are given N number of coordinates and you have to create a polygon from these points such that they will make a polygon with maximum area.
Note: coordinates provided in the input may or may not be in sequential form.
Constraints
1 <= N <= 10
Input:
First line contains an integer N which depicts number of co-ordinates
Next N lines consist of two space separated integer depicting coordinates of in form of xy
Output:
Print the maximum possible area possible by creating a polygon by joining the coordinates.
If the area is in decimal form, print the absolute value as output.
Time Limit (secs):
1
Examples:
Input:
4
0 0
2 0
0 2
2 2
Output:
4
Explanation:
As we can imagine that these points will make a square shape and the maximum possible area made by the polygon will be 4.
import math
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def compare_points(a, b):
if a.x < b.x or (a.x == b.x and a.y < b.y):
return -1
elif a.x == b.x and a.y == b.y:
return 0
else:
return 1
def cross_product(p0, p1, p2):
x1 = p1.x - p0.x
y1 = p1.y - p0.y
x2 = p2.x - p0.x
y2 = p2.y - p0.y
return x1 * y2 - x2 * y1
def convex_hull(points):
n = len(points)
if n <= 3:
return points
points.sort(key=lambda point: (point.x, point.y))
upper_hull = []
lower_hull = []
for i in range(n):
while len(upper_hull) >= 2 and cross_product(upper_hull[-2], upper_hull[-1], points[i]) <= 0:
upper_hull.pop()
upper_hull.append(points[i])
for i in range(n - 1, -1, -1):
while len(lower_hull) >= 2 and cross_product(lower_hull[-2], lower_hull[-1], points[i]) <= 0:
lower_hull.pop()
lower_hull.append(points[i])
upper_hull.pop()
lower_hull.pop()
upper_hull.extend(lower_hull)
return upper_hull
def calculate_area(polygon):
n = len(polygon)
if n < 3:
return 0
area = 0
for i in range(n):
x1 = polygon[i].x
y1 = polygon[i].y
x2 = polygon[(i + 1) % n].x
y2 = polygon[(i + 1) % n].y
area += (x1 * y2 - x2 * y1)
return abs(area) // 2
if __name__ == "__main__":
n = int(input())
points = []
for _ in range(n):
x, y = map(int, input().split())
points.append(Point(x, y))
convex_hull_points = convex_hull(points)
max_area = calculate_area(convex_hull_points)
print(max_area)
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
