You are not logged in. Please login at www.codechef.com to post your questions!

×

INSQ16G - Editorial

PROBLEM LINK:

Contest
Practice

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.

SOLUTION:

Setter's Solution

asked 10 Nov '16, 16:01

vikky_codder's gravatar image

6★vikky_codder
7929
accept rate: 0%

edited 07 Jun '17, 15:34

admin's gravatar image

0★admin ♦♦
19.8k350498541


On following Setter's Solution link, the page says Access Denied. Is that for everyone or just me ?

link

answered 07 Jun '17, 15:38

godslayer12's gravatar image

1★godslayer12
419210
accept rate: 7%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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