Обсуждение @ 1305. Выпуклая оболочка @ Timus Online Judge

Ilya Grebnov[Ivanovo SPU] Can somebody explain to me this problem? [3] // Задача 1305. Выпуклая оболочка 4 сен 2004 16:53

What sequence of broken line’s vertexes should print my program? Give me some hints or tests.

Dmitry 'Diman_YES' Kovalioff. Retired Of course, I can :) (+) [2] // Задача 1305. Выпуклая оболочка 4 сен 2004 21:21

Just find a convex octagon of minimal area which satisfyes the following conditions:

- all the points given are inside it or lay on it's borders
- it's 2 sides are parallel to oX (-)
- it's 2 sides are parallel to oY (|)
- it's 2 sides are 45 degrees to oX (/)
- it's 2 sides are -45 degrees to oX (\)

And then output all the vertices of this figure. There could be 8 vertices, but some of them might be the same (some sides has zero length), so output them only once. So your output is from 1 till 8 vertices.

Very easy statistical solution is O(N) time, O(1) memory.

P.S. I will answer any your question - just mail me.

chhung6 Re: Of course, I can :) (+) // Задача 1305. Выпуклая оболочка 2 июл 2010 01:08

I can only understand the problem statement after reading this thread...

Thanks so much!

Hikmat Ahmedov Little correction // Задача 1305. Выпуклая оболочка 12 мар 2013 16:48

Dmitry 'Diman_YES' Kovalioff. Retired писал(a) 4 сентября 2004 21:21

Just find a convex octagon of minimal area

Area should not be minimal, the number of points inside convex polygon should be minimal, in other words, try so that more points lie on the boundary rather than inside the polygon.

Обсуждение задачи 1305. Выпуклая оболочка