Geometry

This is a pretty interesting topic that I see often in hard math / competitive programming contests. However, I never seem to to be able to solve them.

Learning this more in the context of competitive programming.

In geometric problems, it is often challenging to find a way to approach the problem so that the solution to the problem can be conveniently implemented and the number of special cases is small.

General formula for area of quadrilateral whose: $x_1{y}_2-x_2{y}_1+x_2{y}_3-x_3{y}_2+x_3{y}_4-x_4{y}_3+x_4{y}_1-x_1{y}_4$

Topics

• Area

Actually, you use complex numbers to solve geometry problems??

typedef long long C;
typedef complex<C> P;
#define X real()
#define Y imag()

// Printing x,y, coordinates
P p = {4,2};
cout << p.X << " " << p.Y << "\n"; // 4 2
 
// Summing vectors
P v = {3,1};
P u = {2,2};
P s = v+u;
cout << s.X << " " << s.Y << "\n"; // 5 3
 
// Distance between two points 
P a = {4,2};
P b = {3,-1};
cout << abs(b-a) << "\n"; // 3.16228
 
// Claculate the angle with respect to the x axis
P v = {4,2};
cout << arg(v) << "\n"; // 0.463648
// rotates it 1/2 radians counterclockwise
v *= polar(1.0,0.5); 
cout << arg(v) << "\n"; // 0.963648
 
// Cross Product
P a = {4,2};
P b = {1,2};
C p = (conj(a)*b).Y; // 6

Detecting Line Segment Intersection

This is where your cross product formulas, and Linear Algebra is super helpful.

How do you determine if a point is inside a polygon or outside a polygon? (Pre-req: determine line intersection)

Omg that is such an interesting idea, just send arbitrary rays from the point. If the number of interesctions is odd, then the point is inside the polygon. Else, if it is even, then it is outside the polygon.