Geometry Primitives

You should know operations such as the cross product and dot product.

Standard Problems

To check the $P$ location towards the $P_1$ $P_2$ line we use following formula: $(P.y - P_1.y) * (P_2.x - P_1.x) - (P.x - P_1.x) * (P_2.y - P_1.y)$ If it's equal to $0$ it means that $P$, $P_1$ and $P_2$ are collinear. Otherwise the value's sign indicated if $P$ is under the line - negative - or above the line - positive.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Point Class (Click to expand)

long long collinear(Point p, Point p1, Point p2) {
	return 1LL * (p.y - p1.y) * (p2.x - p1.x) -
	       1LL * (p.x - p1.x) * (p2.y - p1.y);
}

We can quickly dismiss the segment intersection by treating them as rectangles having the segments as diagonals which can be easily done. If it turns out the rectangles intersect then we just check if the segment's ends are on different sides of the other segment.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Point Class (Click to expand)

int sign(long long num) {
	if (num < 0) {
		return -1;
	} else if (num == 0) {
		return 0;

The following algorithm uses the Shoelace formula.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Point Class (Click to expand)

int main() {
	int n;
	cin >> n;
	vector<Point> points(n);
	for (auto &p : points) { cin >> p; }

We can cast a ray from the point $P$ going in any fixed direction (people usually go to the right). If the point is located on the outside of the polygon the ray will intersect its edges an even number of times. If the point is on the inside of the polygon then it will intersect the edge an odd number of times.

This approach is called ray casting.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Point Class (Click to expand)

int sign(long long num) {
	if (num < 0) {
		return -1;
	} else if (num == 0) {
		return 0;

Resources

• My Templates

Misc Problems

Some European Olympiads, like the CEOI, Balkan OI, and the Croatian OI, tend to have a lot of geometry problems. These problems tend to be quite difficult as well, so look for problems there when you run out of problems to practice!