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](http://www.cplusplus.com/reference/complex/).↵
↵
<hr>↵
↵
#### 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.↵
<hr>↵
↵
#### 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)↵
↵
~~~~~↵
↵
<hr>↵
↵
#### 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: `(a.conj(a) * b).x`↵
↵
4. Cross product: `(a.conj(a) * b).y`↵
<br><br><b>notice</b>: <i>conj(a) * b = (ax*bx + ay*by) + i (ax*by — ay*bx)</i>↵
↵
5. Squared distance: `norm(a - b)`↵
↵
6. Euclidean distance:`sqrt(norm(a - b))` or `abs(a - b)`↵
↵
7. Angle of elevation: `arg(b - a)`↵
↵
8. Slope of line (a, b): `tan(arg(b - a))` or `(b-a).y / (b-a).x`↵
↵
9. Polar to cartesian: `polar(r, theta)`↵
↵
10. Cartesian to polar: `point(abs(cartp), arg(cartp))`↵
↵
11. Rotation about the origin: `a * polar(1.0, theta)`↵
↵
12. Rotation about pivot p: `(a-p) * polar(1.0, theta) + p`↵
↵
_**notice**<br><br><b>UPD</b>: added more useful functions↵
↵
13. Angle ABC: `remainder(arg(a-b) - arg(c-b), 2.0 * M_PI)`↵
↵
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() * b == (ax*bx + ay*by) + i (ax*by - ay*bx) = dot(a,b) + i*(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(a,b)`_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 [user:Zlobober,2015-12-19] 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.
↵
**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](http://www.cplusplus.com/reference/complex/).↵
↵
<hr>↵
↵
#### 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.↵
<hr>↵
↵
#### 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)↵
↵
~~~~~↵
↵
<hr>↵
↵
#### 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: `(
↵
4. Cross product: `(
<br><br><b>notice</b>: <i>conj(a) * b = (ax*bx + ay*by) + i (ax*by — ay*bx)</i>↵
↵
5. Squared distance: `norm(a - b)`↵
↵
6. Euclidean distance:
↵
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(
↵
11. Rotation about the origin: `a * polar(1.0, theta)`↵
↵
12. Rotation about pivot p: `(a-p) * polar(1.0, theta) + p`↵
_**notice**
↵
13. Angle ABC: `remainder(arg(a-b) - arg(c-b), 2.0 * M_PI)`↵
↵
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
↵
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(
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 [user:Zlobober,2015-12-19] 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.