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

×

CF224 - Editorial

PROBLEM LINK:

Practice Contest

Author: Sagar
Tester: Karan

DIFFICULTY:

MEDIUM

PROBLEM:

Let's consider a 2D plane, where we plug pegs at the points mentioned. We enclose all the pegs with a elastic band and then release it to take its shape. The closed structure formed by elastic band is similar to that of convex hull. Find the perimeter of the convex hull for the points.

EXPLANATION:

Let points[0..n-1] be the input array.

1) Find the bottom-most point by comparing y coordinate of all points. If there are two points with same y value, then the point with smaller x coordinate value is considered. Let the bottom-most point be P0. Put P0 at first position in output hull.

2) Consider the remaining n-1 points and sort them by polor angle in counterclockwise order around points[0]. If polor angle of two points is same, then put the nearest point first.

3 After sorting, check if two or more points have same angle. If two more points have same angle, then remove all same angle points except the point farthest from P0. Let the size of new array be m.

4) Create an empty stack ‘S’ and push points[0], points[1] and points[2] to S.

5) Process remainning m-3 points one by one.Do following for every point 'points[i]'.
  5.1 Keep removing points from stack while orientation of following 3 is not counterclockwise
      a)Point next to top in stack
      b)Point at the top of stack
      c)points[i]
  5.2 Push points[i] to S
6) Keep removing points from the stack and calculate the distance between the two adjacent points.the sum of all these distances of points will give the perimeter of the polygon

TESTER'S SOLUTION

Ideone

This question is marked "community wiki".

asked 03 Apr '16, 16:05

ishpreet's gravatar image

4★ishpreet
9718
accept rate: 0%

edited 04 Apr '16, 15:16

admin's gravatar image

0★admin ♦♦
19.8k350498541

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,684
×2,596
×153
×14
×8
×1

question asked: 03 Apr '16, 16:05

question was seen: 1,305 times

last updated: 04 Apr '16, 15:16