Problem Link:
Clash Wildcard 2022
Practice
Problem:
You are given co-ordinates of TOM’s room on XY plane, which is a convex polygon as all of the angles formed by adjacent walls of his room are less than 180 degrees.
Find out the amount of cleaning solution required to clean his room if 1 unit of solution is required for cleaning 1 sq. unit of the floor.
Explanation:
Co-ordinates of corners of Tom’s room are given to us in random order. All we have to do is rearrange them in a cyclic order and return the floor of the area.
Original question required the area to be rounded off, but due to unclarity in problem statement, answers with a relative difference of 1 were accepted.
Approach:
In the first step we need to rearrange all the points in clockwise/anti-clockwise manner. For that we sort all the points based on their X co-ordinates.
Next we need to split the polygon into two halves, upper and lower half (halves are created by bisecting the polygon using the line joining the leftmost and the rightmost extreme points of the polygon). So if we choose any random point on the polygon (except the left most and right most point), if it lies above the line, it goes in the upper half, else it
belongs in the lower half.
After adding all the points to upper and lower half, simply reverse the array of lower half and append it to the array of upper half.
The area of this polygon can then be calculated by splitting it into multiple non-overlapping triangles from a fixed point on the polygon, and summing their area.
Setter's Solution (Python)
Python Code:
def triangeArea(x1,y1,x2,y2,x3,y3):
Triange_Area = abs((0.5)*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)))
return Triange_Area
def line(a,b,x):
#This function takes Point A and B, as well as x as input
#and returns y coordinate for the given value of x on the line formed by A and B
m=b[1]-a[1]
m/=b[0]-a[0]
y=b[1]+(m*(x-b[0]))
return y
def rearrange(graph):
# This functions takes coordinates sorted on x axis and returns the cyclic order of polygon
right=graph[-1]
left=graph[0]
upper=[]
lower=[]
for i in range(1,len(graph)-1):
if(graph[i][1]>line(left,right,graph[i][0])):
upper.append(graph[i])
else:
lower.append(graph[i])
return [left]+upper+[right]+lower[::-1]
for _ in range(int(input())):
n=int(input())
all_points=[]
for i in range(n):
x,y=map(int,input().split())
all_points.append([x,y])
all_points.sort()
all_points=rearrange(all_points)
cool_point=all_points[0]
ans=0
for i in range(1,n-1):
ans+=triangeArea(cool_point[0],cool_point[1],all_points[i][0],all_points[i][1],all_points[i+1][0],all_points[i+1][1])
print(int(ans))