## 10797 - Peaceful Sharing

Moderator: Board moderators

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
Ok.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
I guess it depends on coordinate limits, right? like log(DX) * log(DY)

DX=MAXX-MINX, DY=MAXY-MINY

If so, then it's actually O(N*log(DX)*log(DY)) for arbitrary values of X/Y fitting into 'long double' without precision issues. Might be O(N*log(N)) if we can compact space between neighboring X/Y values.

I'll know when I find it
To be the best you must become the best!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I implemented my algorithm in 40 lines, and it's O((log X)*(n log n))
using stl. I can make it faster, but it's not needed to get AC.

phy
New poster
Posts: 3
Joined: Sat Apr 26, 2008 8:41 am

### Re: 10797 - Peaceful Sharing

Could someone explain or introduce something about the term "dual" or "median of arrangement"?
This problem looks interesting. But I just got no idea on solving this...