brycesandlund's blog

Point struct for geometry library
By brycesandlund, history, 8 years ago, In English

(This post is primarily for ACM-ICPC, since you don't need to type in code for online contests.)

My current geometry library uses a Pt struct with members x and y. However, many times I just use a pair instead as this avoids needing to type the struct code and a comparator if you need sorting. However, if you're writing enough geometry functions, it's quicker to write and easier to read with .x and .y instead of .first and .second. I'm now considering doing something like the following:

typedef long long T;
typedef pair<T, T> Pt;
#define x first
#define y second

Pt operator - (Pt a, Pt b) { return Pt(a.x-b.x, a.y-b.y); }

T dot(Pt a, Pt b) { return a.x*b.x + a.y*b.y; }

double dist(Pt a, Pt b) {
    return sqrt(dot(a-b,a-b));
}

This kind of gives the best of both worlds; however, it has some strange side effects. I am wondering if the community has an opinion on what is the best to use, or if there is a different trick I can make use of.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can use std::complex for 2D geometry, here is a blog post about it.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Looks like a good idea, but not working for integral data types is a pretty big drawback. I may include both implementations or just the pair version.

    EDIT: It looks like complex types can't be sorted. Another drawback. I'll probably stick with pairs.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I always use struct P { int x, y; }; because:

  1. If I need some extra info (attribute), e.g. id or weight, I can easily add it.
  2. I can use functions like p1.distToLine(...) or p1.write(), what makes code a bit easier to understand. I wouldn't want write(p1) because it's one more global function, while p1.write() is implemented in the struct — exactly where it belongs.

Also, in your approach you can't use variables named x and y because of your define.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Well, he can, but they will actually become "first" and "second" after preprocessing. This leads to several troubles, like the difficulties while debugging (gdb doesn't understand "print x" and requires you to write "print first" in such a situation), or lack of possibility to write "int x; int first;" in the same scope.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The debugging shouldn't be an issue. And I can avoid using int x; and int first; in the same scope. Overall it seems okay, unless I'm missing another shortcoming.

      → Reply