×

# INSQ16G - Editorial

Author: Manish Kumar Sinha
Editorialist: Manish Kumar Sinha

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.

# SOLUTION:

Setter's Solution

7929
accept rate: 0%

19.8k350498541

 0 On following Setter's Solution link, the page says Access Denied. Is that for everyone or just me ? answered 07 Jun '17, 15:38 419●2●10 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×637
×78
×56
×24

question asked: 10 Nov '16, 16:01

question was seen: 732 times

last updated: 07 Jun '17, 15:38