218 - Moth Eradication : Colinear Points on the Convex Hull

[Julien Cornebise]

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]

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 !!!

[titid_gede]

hi,

i want to ask, what is the output for this :

Code: Select all

3
1 1
2 2
3 3
0


thanks before.

[Julien Cornebise]

Hi.

For

Code: Select all

3
1 1
2 2
3 3
0


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