Advertisement
Published in:
2017 | OriginalPaper | Chapter
13. Geometry
Author : Antti Laaksonen
Published in: Guide to Competitive Programming
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
This chapter discusses algorithm techniques related to geometry. The general goal of the chapter is to find ways to conveniently solve geometric problems, avoiding special cases and tricky implementations. Section 13.1 introduces the C++ complex number class which has useful tools for geometric problems. After this, we will learn to use cross products to solve various problems, such as testing whether two line segments intersect and calculating the distance from a point to a line. Finally, we discuss ways to calculate polygon areas and explore special properties of Manhattan distances. Section 13.2 focuses on sweep line algorithms which play an important role in computational geometry. We will see how to use such algorithms for counting intersection points, finding closest points, and constructing convex hulls.