10095 - Saving the Planet

blue cat · Post by **blue cat** » Sun May 12, 2002 2:23 pm

I've no idea about this problem,can anybody give me a hint.
(Email:flyingbluecat@hotmail.com)

Caesum · Post by **Caesum** » Fri Dec 13, 2002 11:19 pm

hmm, well I start with the minimum bounding box and take the center of it as my center. I then start with maxerr=r/4 and reduce this through a series of loops until its less than epsilon, say 1e-8. On each loop I see if I can nudge the center towards the furthest point and obtain a smaller value for r. It seems to work ok, but I get TLE a lot, and its overall WA at the moment. Anyone got any good suggestions for either:
1. reducing the complexity, ie discarding some points ?
or
2. obtaining a fast convergence towards the center ?

Ivan Golubev · Post by **Ivan Golubev** » Sat Dec 14, 2002 1:12 am

Doesn't it a "finding 3D convex hull" problem?..

Caesum · Post by **Caesum** » Sat Dec 14, 2002 2:24 am

ah, my computational geometry isnt very good. how do you find the minimum bounding sphere from the convex hull ?

Ivan Golubev · Post by **Ivan Golubev** » Sat Dec 14, 2002 3:08 pm

Well, my computational geometry also isn't very good but I think that this problem is very close to P10005 (Packing polygons). For that problem I've used 2D convex hull and 2D centroid algorithms. I think that 3D convex hull and 3D centroid algos will works for P10095. Though 3D convex hull looks a bit complex to implement and I haven't got AC on this one (actually, I haven't even tried to solve it).

As I can understand (a many references goes to it) there is a very good book on CG -- Joseph O'Rourke's "Computational Geometry in C". AFAIR, there was a full source code from this book available to download but I can't remember the exact URL.

Caesum · Post by **Caesum** » Sat Dec 14, 2002 4:25 pm

hmm, i found it here:
http://cs.smith.edu/~orourke/books/compgeom.html
not sure it looks that useful though but i think i need to know more about this.....

windows2k · Post by **windows2k** » Mon Jan 05, 2004 6:33 pm

What's wrong with the problem?
I got accepted before,but it is gone.
Could someone tell me why? Thx

altertain · Post by **altertain** » Fri Feb 02, 2007 9:46 am

If n = 1, what is right answer?

For example,

1
2 3 4

my program returns

0.0000 2.0000 3.0000 4.0000

Is this right?

altertain · Post by **altertain** » Sat Feb 03, 2007 4:10 pm

0.0000 2.0000 3.0000 4.0000

is right.

I got accepted.