10095  Saving the Planet
Moderator: Board moderators
10095  Saving the Planet
I've no idea about this problem,can anybody give me a hint.
(Email:flyingbluecat@hotmail.com)
(Email:flyingbluecat@hotmail.com)
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 1e8. 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 ?
1. reducing the complexity, ie discarding some points ?
or
2. obtaining a fast convergence towards the center ?

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
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.
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.
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.....
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.....