International Collegiate Programming
Contest

Computational Geometry
This session focuses on computational geometry.
If you are not familiar with the relevant concepts and algorithms, or you need a refresher,
you can use the resources below.
Problem Set

Line Segment Distance

Fractal

War on Weather

Board Wrapping

Birthday Cake
Note: All problems expect I/O to be done using standard input and standard
output. The solution to problems must be written in a single file.
If you are programming in Java the application class should be called
"Main".
Geometry problems often can be solved much more easily with appropriate library code.
If you do not have implementations of the most commonly needed functions, we recommend taking
a look at our library code at the following location:
https://github.com/atmorgan/ICPC2014.
In particular, we have the following files:

Vector.cc  Defines
point primitive and distance, cross, and dot products.

PlaneGeometry.cc 
Includes point, line, line segment, and circle intersection, projection, and collinearity tests

Polygon.cc 
Provides functions for polygon area, perimeter, centroid, winding number, and convex hull.
Basic Geometry
Before beginning to work on geometry problems, it is worth familiarizing
yourself with some basic tools. It is highly recommended to begin thinking
of things in terms of dot products and cross products. The following
top coder tutorial
discusses these primitives.
Another basic problem in computational geometry is to determine whether two
(or more) line segments intersect. This
page
has a nice overview of this problem, though it should be read in conjunction
with notes for the later sections.
Do not overuse the trig and inverse trig functions, as they can slow down
your program and introduce precision errors if you use them where it isn't
necessary. The usual recommendation to use integer rather than floatingpoint
arithmetic where possible still stands; though in geometry problems you will
often find yourself using floating point numbers, you might not have to
as much as you think if the inputs are integers.
Convex Hull
One basic problem in plane geometry is finding the convex hull of a set of
points. Recall that a convex region is a region such that any line segment
connecting two points of the region is contained entirely within the region.
The convex hull of a set of points, then, is the
smallest convex region containing all the points.
Since for most purposes, we're interested in points defining
the boundary of that region, we will often denote by the "convex hull"
of a finite set of points the subset of those points which are vertices
of the boundary of the actual convex hull. That is, the "convex
hull" consists of the vertices of the smallest convex polygon such that
every point of the set is either inside or on the boundary of the polygon.
Convex hull problems often involve things like perimeter (the polygon formed
by the convex hull has minimum perimeter among all regions containing all
the points), enclosing area, convexity, and other similar geometric notions.
Also, finding the convex hull can sometimes be useful in other places, e.g.,
to reduce the number of points that need to be taken into consideration
for further processing.
One relatively easytoimplement
algorithm for finding convex hull is called Graham Scan. A succinct
outline of Graham Scan can be found on the Wikipedia page
here.
It runs in O(n log n) time. It is worth
noting that you never actually need to compute any angles; all the sorting
and testing can be done by computing signs of various cross products.
Another wellknown algorithm is Jarvis' walk, also known as
giftwrapping.
Polygon Area
A polygon can be viewed as a sequence of line segments, or as the area
inscribed by them, or as the sequence of endpoints of these line segments
(the vertices of the polygon). A polygon is called simple if the line
segments to not intersect.
There are two very useful formulas for the area of a simple polygon, given its
vertices in order (either clockwise or counterclockwise). The first is
a general formula, based on the fact that the signed area of a plane triangle is
equal to one half the cross product of two of its edges. If we add this up
over all triangles obtained by adjacent vertices in the polygon, we get
A = (1/2)sum(i=1..n : x_{i1}y_{i}  x_{i}y_{i1}),
where p_{i} = (x_{i}, y_{i}) are the vertices of the
polygon, p_{0} = p_{n}, given in clockwise or counterclockwise
order. The area will be negative if the order is clockwise and positive
if the order is counterclockwise.
When the coordinates of all vertices are integer, there is
another nice formula for the area of a simple polygon 
Pick's Theorem.
This theorem states that the area of a simple polygon with vertices only
on the lattice of points with intger coordinates,
is equal to the number of lattice points in its interior, plus
half the number of lattice points on its boundary, minus 1. When a problem
involves lattice polygons, you might think about how you can use this theorem.
Sweep Lines
The notion of a sweep line is a general idea that may be used to make many
geometric problems tractable. The idea is to pass a changing line over
the plane (or in general a surface through space) and do something whenever
it passes a critical point of the problem. This allows a seemingly global
problem to be somewhat localized; you need only keep track of what points
the sweep line is currently passing through plus whatever cumulative
information you've already computed, rather than navigate everything in
the global problem at once. The sweep line can be vertical or horizontal,
moving parallel to an axis, or it can rotate about a fixed point.
Though one imagines the sweep line moving smoothly as it covers the area of
the problem, with the algorithm doing something whenever the sweep line
intersects a critical point, in fact one first sorts all the critical points
and iterates over them. A primer on line sweep algorithms is available
at
this Topcoder tutorial (updated link for 2015).
Line sweep algorithms are not just for geometry! Indeed, many kinds of
interval algorithms can be thought of as line sweep algorithms (for instance,
determining the clique number of an interval graph). If you can focus your
attention on certain critical points, and do all your work as some local work
at each critical point plus some cumulative information, then the line sweeping
idea may apply.
