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

• My Templates

Location of a Point

Explanation

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

Time Complexity: $\mathcal{O}(1)$ for each test case.

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);
}

int main() {

Copy
class Point:
	def __init__(self, x: int = 0, y: int = 0):
		self.x = x
		self.y = y


def collinear(p: Point, p1: Point, p2: Point) -> int:
	return (p.y - p1.y) * (p2.x - p1.x) - (p.x - p1.x) * (p2.y - p1.y)

Segment Intersection

Explanation

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;

Polygon Area

Explanation

We can use the Shoelace formula.

Implementation

Time Complexity: $\mathcal{O}(N)$

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; }

Copy
class Point:
	def __init__(self, x: int = 0, y: int = 0):
		self.x = x
		self.y = y


n = int(input())
points = []
for _ in range(n):
	x, y = map(int, input().split())

Point's Location Relative to Polygon

Explanation

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)

bool on_segment(const Point &p, const Point &p1, const Point &p2) {
	int a = min(p1.x, p2.x);
	int b = max(p1.x, p2.x);
	int x = min(p1.y, p2.y);

Lattice points in polygon

Explanation

Let's first focus on the lattice points on the polygon's boundary. We'll process each edge individually. The number of intersections of a line with lattice points is the greatest common divisor of $P_1.x - P_2.x$ and $P_1.y - P_2.y$.

Now that we know the number of lattice points on the boundary we can find the number of lattice points inside the polygon using Pick's theorem. Let's denote $A$ polygon's area, $i$ the number of integer points inside and $b$ the number of integer points on its boundary. Then, according to Pick's theorem, we have the following equation: $A = i + b/2 - 1$. Changing the order a little bit to get $i = A - b/2 + 1$. We've found $b$ and, as you've probably already solved Polygon Area from above, $A$ can be computed using cross-product.

Implementation

Time Complexity: $\mathcal{O}(N \log P)$, where $P$ is the maximum difference between coordinates of points.

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);

Copy
from math import gcd


class Point:
	def __init__(self, x: int = 0, y: int = 0):
		self.x = x
		self.y = y

	def __sub__(self, other):
		return Point(self.x - other.x, self.y - other.y)

Angles

Explanation

Working with angles only makes sense in the context of lines and segments. Therefore, let's consider the segments connecting the initial position and each dot: $(pos_x, pos_y)-(x, y)$. One such segment is inside the field of view if and only if its slope is bigger than the lower bound and smaller than the upper bound. Since we're working with angles, we'll convert the slopes into radians.

Consider $\alpha$ as the angle formed by one line with the $\texttt{ox}$ axis. Then we have:

The movement of the field of view can be seen as a sliding window applied on the sorted angles of the points. The angle of the field of vies could be large enough to see points from the beginning of the sorted array, thus the array of angles should be duplicated - cyclic array.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
class Solution {
  public:
	int visiblePoints(vector<vector<int>> &points, int angle, vector<int> &location) {
		int extra = 0;
		vector<double> angles;
		for (const vector<int> &p : points) {
			// Ignore points identical to location
			if (p == location) {
				extra++;
				continue;

Copy
class Solution:
	def visiblePoints(
		self, points: List[List[int]], angle: int, location: List[int]
	) -> int:
		extra = 0
		angles = []

		for p in points:
			# Ignore points identical to location
			if p == location:

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!