10797 - Peaceful Sharing

[Destination Goa]

Ok.

[Destination Goa]

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

[sclo]

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]

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

Thanks in advance.