Compressing the coordinates is the most obvious solution and it's hard to name this approach "data structures"...

The guys like me who AC'ed it with any more stupid idea like straightforward implementation on vector are offended in their best feelings. :-)