Geometry in competitive programming Dissertation presented by Victor L ECOMTE for obtaining the master's degree in Computer Science and Engineering Supervisor Yves D EVILLE Co-supervisor François A UBRY Readers François A , Yves D , Jean-François R UBRY EVILLE EMACLE Academic year 2017-2018 Abstract Competitive programming consists in the organization of programming con- tests, which see the world’s most talented coders compete to solve problems of an algorithmic nature by implementing efficient programs as quickly as possible. Recently, geometry problems have had an increasing importance in those contests, but many contestants dislike them for being too technical or causing too precision issues linked to the use of floating-point numbers. We believe that those complaints are for the largest part due to a lack of specific training on the basics of computational geometry. We therefore introduce a new handbook of computational geometry, aimed primarily at the competitive programming public. It treats the subject in a practice- oriented way, providing code snippets for every operation, and explaining theminintuitivetermswiththehelpofalargeamountofillustrativefigures. Its contents focus on the foundations of both 2D and 3D computational geometry, as well as the management of floating-point imprecisions, where we present a model of error propagation based on magnitude conditions and dimensionality of values. In addition, we present an original geometry contest whose problems showcase innovative notions and techniques, especially in 3D geometry. We hope that in the future, problem setters can reuse and adapt those ideas in order to foster variety and expand the scope of geometry as a competitive programming subfield. Contents I Main contents 6 1 Introduction 7 1.1 About competitive programming . . . . . . . . . . . . . . . . 7 1.2 Types of programming contests . . . . . . . . . . . . . . . . . 8 1.3 Geometry in competitive programming . . . . . . . . . . . . . 9 1.4 Goals and structure of this thesis . . . . . . . . . . . . . . . . 9 2 Writing a handbook of geometry 11 2.1 Approach and writing style . . . . . . . . . . . . . . . . . . . 11 2.2 Current contents . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Publication and future plans . . . . . . . . . . . . . . . . . . 13 3 Organizing a geometry contest 14 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Introduction to contest preparation . . . . . . . . . . . . . . . 14 3.3 Presentation of the problems . . . . . . . . . . . . . . . . . . 17 3.4 Problem statements . . . . . . . . . . . . . . . . . . . . . . . 18 3.5 Editorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5.1 Sledding down the mountain . . . . . . . . . . . . . . 34 3.5.2 Pen spinning accident . . . . . . . . . . . . . . . . . . 36 3.5.3 Polar map . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.5.4 Gold paint optimization . . . . . . . . . . . . . . . . . 40 3.6 Results and conclusion . . . . . . . . . . . . . . . . . . . . . . 43 4 Conclusion 45 1 II Handbook of geometry for competitive programmers 47 5 Precision issues and epsilons 48 5.1 Small imprecisions can become big imprecisions . . . . . . . . 48 5.1.1 When doing numerically unstable computations . . . . 49 5.1.2 With large values and accumulation . . . . . . . . . . 50 5.2 Small imprecisions can break algorithms . . . . . . . . . . . . 51 5.2.1 When making binary decisions . . . . . . . . . . . . . 51 5.2.2 By violating basic assumptions . . . . . . . . . . . . . 52 5.3 Modelling precision . . . . . . . . . . . . . . . . . . . . . . . . 52 5.3.1 The issue with “absolute or relative” error . . . . . . . 52 5.3.2 Precision guarantees from IEEE 754 . . . . . . . . . . 54 5.3.3 Considering the biggest possible magnitude . . . . . . 54 5.3.4 Incorporating multiplication . . . . . . . . . . . . . . . 55 5.3.5 Why other operations do not work as well . . . . . . . 56 5.4 Case studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.4.1 Problem “Keeping the Dogs Apart” . . . . . . . . . . 57 5.4.2 Quadratic equation . . . . . . . . . . . . . . . . . . . . 62 5.4.3 Circle-circle intersection . . . . . . . . . . . . . . . . . 64 5.5 Some advice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.5.1 For problem solvers . . . . . . . . . . . . . . . . . . . 67 5.5.2 For problem setters. . . . . . . . . . . . . . . . . . . . 68 6 Basics 69 6.1 Points and vectors . . . . . . . . . . . . . . . . . . . . . . . . 69 6.1.1 Complex numbers . . . . . . . . . . . . . . . . . . . . 69 6.1.2 Point representation . . . . . . . . . . . . . . . . . . . 72 6.2 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2.1 Translation . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2.2 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.2.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.2.4 General linear transformation . . . . . . . . . . . . . . 77 6.3 Products and angles . . . . . . . . . . . . . . . . . . . . . . . 78 6.3.1 Dot product . . . . . . . . . . . . . . . . . . . . . . . . 78 2 6.3.2 Cross product . . . . . . . . . . . . . . . . . . . . . . . 80 6.4 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.4.1 Line representation . . . . . . . . . . . . . . . . . . . . 86 6.4.2 Side and distance . . . . . . . . . . . . . . . . . . . . . 89 6.4.3 Perpendicular through a point . . . . . . . . . . . . . 90 6.4.4 Sorting along a line . . . . . . . . . . . . . . . . . . . 90 6.4.5 Translating a line . . . . . . . . . . . . . . . . . . . . . 91 6.4.6 Line intersection . . . . . . . . . . . . . . . . . . . . . 92 6.4.7 Orthogonal projection and reflection . . . . . . . . . . 93 6.4.8 Angle bisectors . . . . . . . . . . . . . . . . . . . . . . 93 6.5 Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.5.1 Point on segment . . . . . . . . . . . . . . . . . . . . . 95 6.5.2 Segment-segment intersection . . . . . . . . . . . . . . 96 6.5.3 Segment-point distance . . . . . . . . . . . . . . . . . 98 6.5.4 Segment-segment distance . . . . . . . . . . . . . . . . 98 6.6 Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.6.1 Polygon area . . . . . . . . . . . . . . . . . . . . . . . 99 6.6.2 Cutting-ray test . . . . . . . . . . . . . . . . . . . . . 101 6.6.3 Winding number . . . . . . . . . . . . . . . . . . . . . 103 6.7 Circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.7.1 Defining a circle . . . . . . . . . . . . . . . . . . . . . 108 6.7.2 Circumcircle . . . . . . . . . . . . . . . . . . . . . . . 108 6.7.3 Circle-line intersection . . . . . . . . . . . . . . . . . . 109 6.7.4 Circle-circle intersection . . . . . . . . . . . . . . . . . 111 6.7.5 Tangent lines . . . . . . . . . . . . . . . . . . . . . . . 112 7 3D geometry 116 7.1 Points, products and orientation . . . . . . . . . . . . . . . . 116 7.1.1 Point representation . . . . . . . . . . . . . . . . . . . 116 7.1.2 Dot product . . . . . . . . . . . . . . . . . . . . . . . . 117 7.1.3 Cross product . . . . . . . . . . . . . . . . . . . . . . . 118 7.1.4 Mixed product and orientation . . . . . . . . . . . . . 120 7.2 Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.2.1 Defining planes . . . . . . . . . . . . . . . . . . . . . . 122 3 7.2.2 Side and distance . . . . . . . . . . . . . . . . . . . . . 123 7.2.3 Translating a plane . . . . . . . . . . . . . . . . . . . . 124 7.2.4 Orthogonal projection and reflection . . . . . . . . . . 125 7.2.5 Coordinate system based on a plane . . . . . . . . . . 125 7.3 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.3.1 Line representation . . . . . . . . . . . . . . . . . . . . 127 7.3.2 Distance from a line . . . . . . . . . . . . . . . . . . . 129 7.3.3 Sorting along a line . . . . . . . . . . . . . . . . . . . 129 7.3.4 Orthogonal projection and reflection . . . . . . . . . . 129 7.3.5 Plane-line intersection . . . . . . . . . . . . . . . . . . 130 7.3.6 Plane-plane intersection . . . . . . . . . . . . . . . . . 131 7.3.7 Line-line distance and nearest points . . . . . . . . . . 132 7.4 Angles between planes and lines. . . . . . . . . . . . . . . . . 134 7.4.1 Between two planes . . . . . . . . . . . . . . . . . . . 134 7.4.2 Between two lines . . . . . . . . . . . . . . . . . . . . 135 7.4.3 Between a plane and a line . . . . . . . . . . . . . . . 136 7.4.4 Perpendicular through a point . . . . . . . . . . . . . 136 7.5 Polyhedrons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.5.2 Surface area . . . . . . . . . . . . . . . . . . . . . . . . 138 7.5.3 Face orientation . . . . . . . . . . . . . . . . . . . . . 140 7.5.4 Volume . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.6 Spherical geometry . . . . . . . . . . . . . . . . . . . . . . . . 144 7.6.1 Spherical coordinate system . . . . . . . . . . . . . . . 144 7.6.2 Sphere-line intersection . . . . . . . . . . . . . . . . . 145 7.6.3 Great-circle distance . . . . . . . . . . . . . . . . . . . 146 7.6.4 Spherical segment intersection . . . . . . . . . . . . . 147 7.6.5 Angles on a sphere . . . . . . . . . . . . . . . . . . . . 151 7.6.6 Spherical polygons and area . . . . . . . . . . . . . . . 152 7.6.7 Solid angle . . . . . . . . . . . . . . . . . . . . . . . . 154 7.6.8 3D winding number . . . . . . . . . . . . . . . . . . . 155 A Solutions to the exercises 157 4 B Omitted proofs 160 B.1 Precision bounds for +, , . . . . . . . . . . . . . . . . . . . 160 − × 5 Part I Main contents 6 Chapter 1 Introduction In this chapter, we give a short introduction to competitive programming and the role of geometry in it, then outline the goals and structure of this thesis. 1.1 About competitive programming Competitive programming is the participation in programming contests, which test the participants’ ability to write programs that solve problems of an algorithmic or mathematical nature in an efficient way. Atypicalproblem in aprogrammingcontestdescribesthe problem tobe solved, specifies how the input data is provided and how the output should be written. The participant then has to write a program that will read the input data (typically in stdin), compute the result, then write the output (typically in stdout). When the participant submits a program, it will be compiled by the judging system then executed on a batch of tests, which is designed to comprehensively test the program in many situations and detect any flaw. If for each test case the program runs successfully within the time and memory limits, and the judging system evaluates the answer as correct, then the solution is Accepted and awarded points. Other verdicts include Wrong answer if the output is incorrect, Time limit exceeded if the program took too much time, or Runtime error if the program crashed. Besidesthisstandard”readinput,computeresult,writeoutput”scheme, there are also interactive tasks, in which the participant’s solution has to interact directly with the judging system, exchanging information back and forth. Also, in most tasks, finding a fast enough solution is the main chal- lenge, there are some tasks in which the memory limit might be quite limit- ing, or some other resource determined by the problem statement (like the 7 number of queries the solution may ask the judging system, in interactive tasks). Contestants are free to implement their solutions in a variety of lan- guages, but C++ is the most popular, because of its execution speed and relatively rich standard library. To succeed in contests, good implementa- tion skills and a mastery of the language used are as important as talent in algorithm design and problem solving. For more details about competitive programming, see [4]. 1.2 Types of programming contests Programming contests can be mostly classified under four categories. The type of problems is generally the same across the board, but the contest formats vary a lot. Olympiads in Informatics Often called OIs, olympiads in informatics are contests for secondary school students. The most famous OI is the IOI (InternationalOlympiadinInformatics), heldeveryyearforaboutaweekin thesummer. NationalOIsorganizedinmostcountries,usuallyaspartofthe selection process for IOI, and there are also many regional OIs, like APIO (Asia-Pacific), Balkan OI, CEOI (Central Europe), etc. OIs are individual contests and are characterized by relatively few tasks (at IOI, 3 tasks for 5 hours), each containing many subtasks that give partial score to partial or suboptimal solutions. ACM-ICPC Composed of the World Finals, dozens of regionals serving as qualifiers, and many subregionals for local practice, the ACM-ICPC con- tests are for teams of 3 university students. Teams have 5 hours to solve usually 9-13 problems. All problems are worth 1 point even though their difficulty varies greatly, and ties are broken with submission times, so speed is key. There is no partial score. Regular online contests A handful of websites hold regular individual contests all through the year, at a rate of about one contest per week. Fa- mous contest platforms include Codeforces, AtCoder, CodeChef and CS Academy. Those contests are usually about 2 hours in length, with 4-5 problems whose score varies according to the difficulty. Although the con- tests are mostly for fun, after the contest, the contestants’ rating, which is a reflection of their recent performance, is updated. 8