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

×

Can anyone help me with Protecting Sheep from Dementia 2012 - IIT Mandi Contest?

Hello friends can someone tell me how to approach this problem ??

@vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299 @meooow @john_smith_3

asked 15 Apr, 14:42

harrypotter0's gravatar image

3★harrypotter0
1499
accept rate: 2%


It is a problem on convex-hull.

First try solving this problem. You will get the basic idea, and then you can easily implement the algorithm in this problem.

Jarvis March Algorithm is sufficient for the given constraints.

In this particular question, it is mentioned that "each of the sheep is inside a square of side 2 units" && "Note that the orientation of all of these squares is identical, and the coordinate system has been selected so that each of the sides are parallel to one of the axes", which essentially means that, for each sheep co-ord. (x, y), you need to consider 4 co-ord.s, namely (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1) in your convex-hull algorithm.

If you are still not able to solve it, try to understand this code by @madguy02 .

Video Tutorial of the algorithm can be found here.

link

answered 15 Apr, 16:13

meetrockstar's gravatar image

4★meetrockstar
13114
accept rate: 12%

edited 15 Apr, 16:22

thankyou. Now i got it:)

(16 Apr, 06:58) harrypotter03★
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:

×2,221
×1,881
×76
×7

question asked: 15 Apr, 14:42

question was seen: 70 times

last updated: 16 Apr, 06:58