PROBLEM LINK:
Author: Manish Kumar Sinha
Tester: Asim Krishna Prasad
Editorialist: Manish Kumar Sinha
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Geometry, Line-sweeping
PROBLEM:
Given the corners of a number of polygons, calculate the area and perimeter of the polygon. Also the sides of polygons are parallel to X-axis and Y-axis and none of the polygons intersect.
EXPLANATION:
First thing to observe that sides are parallel to the coordinate axes and polygons are non intersecting, so at a particular value of X or Y, there must be even number of points. So take a vertical line to sweep and maintain active set of points with y ordinate only. At a particular value X, first count the number of points, if it is odd then given region cannot be closed, hence print “Impossible”. Otherwise calculate the area till this X, by iterating through the points in active set.
Calculating Area till X:
Maintain prevX (previous value of X ordinate in case you are sweeping vertical line). At sweep line x = A, iterate through the active set of points(sorted by y-ordinate) and take every pair of points and calculate area by
Area += (A - prevX) * (active[i+1] - active[i]); i += 2;For calculating the perimeter, we have to sweep first using vertical and hen horizontal line. For a vertical sweep line, at a particular X, if we find a point having y ordinate already in the active set, then this a side of a polygon, hence add its length to the perimeter. For vertical sweep line, all the sides which are parallel to x-axis will be added to the perimeter. So for sides parallel to Y-axis, sweep horizontal line and do same.