Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя Hikari9

Автор Hikari9, история, 8 лет назад, По-английски

It's always a hassle to define our 2D Geometry library during a contest. Is there a way to make our computational geometry lives easier in any way? Fortunately for us, there is, at least in C++, using complex numbers.

Complex numbers are of the form a + bi, where a is the real part and b imaginary. Thus, we can let a be the x-coordinate and b be the y-coordinate. Whelp, complex numbers can be represented as 2D vectors! Therefore, we can use complex numbers to define a point instead of defining the class ourselves. You can look at std::complex reference here.


Defining our point class

We can define our point class by typing typedef complex<double> point; at the start of our program. To access our x- and y-coordinates, we can macro the real() and imag() functions by using #define. Of course, don't forget to #include <complex> before anything.

#include <iostream>
#include <complex>
using namespace std;

// define x, y as real(), imag()
typedef complex<double> point;
#define x real()
#define y imag()

// sample program
int main() {
	point a = 2;
	point b(3, 7);
	cout << a << ' ' << b << endl; // (2, 0) (3, 7)
	cout << a + b << endl;         // (5, 7)
}

Oh goodie! We can use std:cout for debugging! We can also add points as vectors without having to define operator+. Nifty. And apparently, we can overall add points, subtract points, do scalar multiplication without defining any operator. Very nifty indeed.


Example

point a(3, 2), b(2, -7);

// vector addition and subtraction
cout << a + b << endl;   // (5,-5)
cout << a - b << endl;   // (1,9)

// scalar multiplication
cout << 3.0 * a << endl; // (9,6)
cout << a / 5.0 << endl; // (0.6,0.4)


Functions using std::complex

What else can we do with complex numbers? Well, there's a lot that is really easy to code.

  1. Vector addition: a + b

  2. Scalar multiplication: r * a

  3. Dot product: (conj(a) * b).x

  4. Cross product: (conj(a) * b).y

    notice: conj(a) * b = (ax*bx + ay*by) + i (ax*by — ay*bx)

  5. Squared distance: norm(a - b)

  6. Euclidean distance: abs(a - b)

  7. Angle of elevation: arg(b - a)

  8. Slope of line (a, b): tan(arg(b - a))

  9. Polar to cartesian: polar(r, theta)

  10. Cartesian to polar: point(abs(p), arg(p))

  11. Rotation about the origin: a * polar(1.0, theta)

  12. Rotation about pivot p: (a-p) * polar(1.0, theta) + p

    UPD: added more useful functions

  13. Angle ABC: abs(remainder(arg(a-b) - arg(c-b), 2.0 * M_PI))

    remainder normalizes the angle to be between [-PI, PI]. Thus, we can get the positive non-reflex angle by taking its abs value.

  14. Project p onto vector v: v * dot(p, v) / norm(v);

  15. Project p onto line (a, b): a + (b - a) * dot(p - a, b - a) / norm(b - a)

  16. Reflect p across line (a, b): a + conj((p - a) / (b - a)) * (b - a)

  17. Intersection of line (a, b) and (p, q):

point intersection(point a, point b, point p, point q) {
  double c1 = cross(p - a, b - a), c2 = cross(q - a, b - a);
  return (c1 * q - c2 * p) / (c1 - c2); // undefined if parallel
}

Drawbacks

Using std::complex is very advantageous, but it has one disadvantage: you can't use std::cin or scanf. Also, if we macro x and y, we can't use them as variables. But that's rather minor, don't you think?

EDIT: Credits to Zlobober for pointing out that std::complex has issues with integral data types. The library will work for simple arithmetic like vector addition and such, but not for polar or abs. It will compile but there will be some errors in correctness! The tip then is to rely on the library only if you're using floating point data all throughout.

  • Проголосовать: нравится
  • +202
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

I've used std::complex as a geometry primitive before, but there is a serious disatvantage: by using it, you can't perform operations in integral data types. I always prefer using my own integral vectors when the task allows it (also some tasks simply can't be solved in doubles).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Hikari9 (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Hikari9 (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really nice reference list! :)

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

To use cin, we just need to overload the operator. I don't see a problem with this in competitions:

template<class T>
istream& operator>> (istream& is, complex<T>& p) {
  T value;
  is >> value;
  p.real(value);
  is >> value;
  p.imag(value);
  return is;
}

int main() {
  point a;
  cin >> a;
  cout << a << endl;
  return 0;
}
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think p.real(value) and p.imag(value) only works for C++11, but yeah, most competitions have C++11 compilers anyway so this is a good suggestion.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just for reference, polar(r, theta) is equal to r * exp(point(0, theta)), which is cool because it obeys the Euler's identity.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

どもうありがとう

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  1. Angle of elevation

I don't get this one... What is it?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    The arctan of the slope of the line connecting a and b. In other words, the angle that the line connecting a and b forms with the x-axis in positive direction.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Suggestion: Instead of using #define x real() and #define y imag() it's easier to use #define x() real() and #define y() imag() so that you can use x() and y() as getter methods without having to remember to always avoid using the variables x and y in other contexts, especially if you include this code in a template.

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

The problem with geometry isn't in such technical details, it's the thousands of special cases you have to watch out for :D.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there a way to implement the less-than function such that the following code runs?

vector<complex<double>> v;
sort(v.begin(),v.end());
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    typedef complex<double> point;
    namespace std
    {
        bool operator <(const point& a, const point& b)
        {
            return real(a) != real(b) ? real(a) < real(b) : imag(a) <
                   imag(b);
        }
    }
    
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Much appreciated :)

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      It may be helpful to avoid round-off floating-point approximation errors when using the != operator to compare the real parts of the complex numbers. The following update in lines 21-23 should fix this issue: Easy geometry