P T H I N K F A ST S

Competitive Programming
From Problem 2 Solution in O(1)

Computational Geometry
Introduction

Mostafa Saad Ibrahim

PhD Student @ Simon Fraser University
 Geometry

About shape, size, relative position of figures

Euclid is the father of geometry

Src: http://previews.123rf.com/images/olgamakarova/olgamakarova1202/olgamakarova120200006/12195518-Geometry-seamless-pattern-Tile-for-endless-background-Stock-Vector.jpg
 Computational Geometry

Study of algorithms for geometric problems.

Our Major focus on 2D. Few 3D.
- 3D algorithms may be more complex
- Or much more computations
- So rare in competitions

Real life apps:

- Games
- Graphics and visualization
- Geographic information systems
- More

Src: http://kiharalab.org/3d-surfer/v1.0/convex_hull.gif http://www.ams.org/featurecolumn/images/august2006/diagramintro.1.jpg http://articles.leetcode.com/wp-content/uploads/2011/05/overlap_rect1.gif

Competitions

◼ Typically 0/1 geometry problem.

◼ Typically guys avoid it if hard problem
◼ Corner Cases
◼ Lines: Vertical?
◼ Points: Collinear?
◼ Polyong: Simple? Concave? ..
◼ Degenerate Cases
◼ Line start and end point are same!
◼ Precision Problems (avoid as possible)
◼ Lots of new coding? Library copy paste?
Resources

◼ Books
◼ Programming Challenges
◼ Competitive Programming
◼ Introduction to Algorithms
◼ http://geomalgorithms.com/algorithms.html
◼ Great site: algorithms and codes
◼ Articles
◼ Topcoder: article 1, article 2
◼ Libraries: lots on web
◼ Lib 1, Lib 2
◼ Mine will be covered by end of series
Elements

Src: http://geobraniacs.wikispaces.com/file/view/Points-Lines-%26-Planes.gif/90029611/Points-Lines-%26-Planes.gif
Trigonometry

◼ All about angles and their measures

◼ Angles measure
◼ Radians: 0 - 2 π
◼ Degrees: 0 - 360
◼ Radians is better computationally - so libraries use that
◼ Right angle 90 degree or π/2 radians
◼ 370 Degree = 10 Degree = 370 % 360
Radians ⇔ Degrees
Radians ⇔ Degrees
Angles
Angles

Src: http://schoolbag.info/sat/sat_3/73.html
Angles
Angles
360 / # sides if all equal

Src: http://www.debate.org/photos/albums/1/6/5244/257096-5244-a4bzy-a.jpg
Triangles Types

Src: https://s3-ap-southeast-1.amazonaws.com/learnhive/lcards/Types-of-Triangles-521dd275368b9.png
Triangle Laws

Src: http://www.mathwarehouse.com/trigonometry/images/law-of-cosines/law-of-cosines-formula-and-picture2.png
Solving Triangles

◼ Given A(angles) or S(sides) of triangle

◼ Find other missing values
◼ 6 different cases!
◼ AAA, AAS, ASA, SAS, SSA, SSS
◼ We mainly use the triangle laws
◼ Homework: Study them and following code
Solving Triangles

Src: http://www.mathwarehouse.com/trigonometry/law-of-sines/images/law-of-sines-and-cosines/law-of-sines-and-cosines-picture.png
Solving Triangles
Trigonometric functions

Src: http://images.slideplayer.com/30/9560908/slides/slide_12.jpg
Trigonometric functions

Src: http://amsi.org.au/ESA_Senior_Years/SeniorTopic2/2d/2d_2content_6.html
Trigonometric formula

Src: http://images.slideplayer.com/2/1035617/slides/slide_1.jpg
Trigonometric functions in C++

◼ In cmath header .. all in radians

◼ Please read the 2 tables..see examples
◼ Revise input/output ranges...vary much
Atan vs Atan 2

Atan range is [-PI/2 - PI/2]

Tan of either angles 45 or 135 => positive values?!
How to know the quadrant! We need to use sin/cos too

atan2(y, x) do that for us and return range [-PI, PI]

Src: http://stackoverflow.com/questions/283406/what-is-the-difference-between-atan-and-atan2-in-c
Atan vs Atan 2
Degree = Radian
------------------------
0=0
90 = 1.5708
180 = 3.14159
270 = 4.71239
360 = 6.28319

45 = 0.785398
135 = 2.35619
225 = 3.92699
315 = 5.49779

1.4 = sqrt(2)

Src: http://stackoverflow.com/questions/283406/what-is-the-difference-between-atan-and-atan2-in-c
Triangle Area

◼ Please read triangle article.

◼ Ignore hard things
◼ Homeworks
◼ Given 3 sides of triangle, find area?
◼ Given the length of three medians of a triangle, find area?
◼ Given 3 sides of triangle inside/outside circle? what is
circle radius? Totally touching the circle
◼ ...
Triangle Area
Circles

Src: http://ssepkowitz.pbworks.com/f/1241790691/SAT_Geometry_Circles1.png
Circles

Src: http://images.slideplayer.com/18/6070989/slides/slide_4.jpg
Circles

Src: http://img1.wikia.nocookie.net/__cb20140723160517/central/images/4/4d/Circle-formuasl-.jpg https://upload.wikimedia.org/wikipedia/commons/thumb/c/ce/Circle_Area.svg/220px-Circle_Area.svg.png

Circles

Src: http://thearclengthofacircle.weebly.com/uploads/1/2/3/3/12338358/3055696.gif?160
Circles
Circles

Src: http://www.funmaths.com/math_tutorials/images/tutorial_geometry6_clip_image002.jpg http://www.mathwarehouse.com/geometry/circle/images/secant-tangent-sides/secant-tangent-side-picture.gif

 ‫ﺗﻢ ﺑﺤﻤﺪ ﷲ‬

‫ﻋﻠﻤﻜﻢ ﷲ ﻣﺎ ﯾﻨﻔﻌﻜﻢ‬

‫وﻧﻔﻌﻜﻢ ﺑﻤﺎ ﺗﻌﻠﻤﺘﻢ‬

‫وزادﻛﻢ ﻋﻠﻤﺎ ً‬