## 218 - Moth Eradication : Colinear Points on the Convex Hull

All about problems in Volume II. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

### 218 - Moth Eradication : Colinear Points on the Convex Hull

Hi

I'm opening a new topic about 218 (Moth Eradication) in order to clearly ask a question that can be, I think, useful to many.

If we have colinear points on the convex hull, do we have to output all of them, or only the two extremities ?

I'm Using Gries and Stojmenovic version of Graham scan (as explained in Programming Challenges, p. 316), wich suppresses such points, and I don't manage to modify it in order to let them be in all the cases.
Could anyone help me please ? This is my first Convex Hull...

Thanks in advance !
Julien Cornebise
Experienced poster

Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France

I finally got AC !
All colinear points should be present in the convex hull.
I finally used Graham's algorithm, just as mentionned above, and then added a piece of code to add ignored colinear points, because modifying the basis algorithm to include colinear points revealed to be a real pain.

But if anybody has another idea (I'm sure there's much better things to do, I'm not as good as I'd like to be), please say !!!
Julien Cornebise
Experienced poster

Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France

hi,

i want to ask, what is the output for this :
Code: Select all
`31 12 23 30`

thanks before.
Kalo mau kaya, buat apa sekolah?
titid_gede
Experienced poster

Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Hi.

For

Code: Select all
`31 12 23 30`

my AC prog answers :

Code: Select all
`Region #1:(1.0,1.0)-(2.0,2.0)-(3.0,3.0)-(1.0,1.0)Perimeter length = 5.66`
Julien Cornebise
Experienced poster

Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France

Return to Volume II

### Who is online

Users browsing this forum: No registered users and 0 guests