10095 - Saving the Planet

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10095 - Saving the Planet

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

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

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

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:

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

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

10095

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 :D

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

..

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?
Lee, Taeyoon

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

right.

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

0.0000 2.0000 3.0000 4.0000

is right.

I got accepted. :D
Lee, Taeyoon

Post Reply

Return to “Volume 100 (10000-10099)”