## 10095 - Saving the Planet

Moderator: Board moderators

blue cat
New poster
Posts: 3
Joined: Tue Apr 09, 2002 6:03 am

### 10095 - Saving the Planet

(Email:flyingbluecat@hotmail.com)

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Doesn't it a "finding 3D convex hull" problem?..

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
ah, my computational geometry isnt very good. how do you find the minimum bounding sphere from the convex hull ?

Ivan Golubev
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.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### 10095

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

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 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?
Lee, Taeyoon

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

### right.

0.0000 2.0000 3.0000 4.0000

is right.

I got accepted.
Lee, Taeyoon