PrevNext
Rare
 0/13

Geometry Primitives

Authors: Mihnea Brebenel, Benjamin Qi

Basic setup for geometry problems.

Edit This Page

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

Standard Problems

Location of a point

Focus Problem – try your best to solve this problem before continuing!

To check the PP location towards the P1P_1 P2P_2 line we use following formula: (P.yP1.y)(P2.xP1.x)(P.xP1.x)(P2.yP1.y)(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 00 it means that PP, P1P_1 and P2P_2 are collinear. Otherwise the value's sign indicated if PP is under the line - negative - or above the line - positive.

Demonstration

Implementation

C++

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

Segment intersection

Focus Problem – try your best to solve this problem before continuing!

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

C++

#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

Focus Problem – try your best to solve this problem before continuing!

The following algorithm uses the Shoelace formula.

Implementation

C++

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

Point's location relative to polygon

Focus Problem – try your best to solve this problem before continuing!

We can cast a ray from the point PP 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

C++

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

Lattice points in polygon

Focus Problem – try your best to solve this problem before continuing!

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 P1.xP2.xP_1.x - P_2.x and P1.yP2.yP_1.y - P_2.y.

Demonstration

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 AA polygon's area, ii the number of integer points inside and bb the number of integer points on its boundary. Then, according to Pick's theorem, we have the following equation: A=i+b/21A = i + b/2 - 1. Changing the order a little bit to get i=Ab/2+1i = A - b/2 + 1. We've found bb and, as you've probably already solved Polygon Area from above, AA can be computed using cross-product.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;
Code Snippet: Point Class (Click to expand)
int main() {
int n;
cin >> n;
vector<Point> points(n);
StatusSourceProblem NameDifficultyTags
YSEasy
KattisEasy
KattisEasy
KattisEasy
KattisEasy

Resources

Resources
CF

short description of operations

CPH

Complex #s, Points & Lines, Polygons, Distances

CF

code, examples

cp-algo
CPC

basics, polygon area, point in polygon

CF

some material is quite advanced

CP2

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!

StatusSourceProblem NameDifficultyTags
CFHard
KattisHard
KattisHard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext