Competitive/Collaborative Programming Class

Contents

• Geometry and Computational Geometry References
• Area of Polygon
• Equation of a Line
• Is a Point ona Line?
• Intersecton of Two Lines
• Intersection of a Line and a Circle

Geometry and Computational Geometry References

• Brief summary of Geometry stuff (3 pages) by Eugene Fink
• Competitive Programmer’s Handbook by Antti Laaksonen (see pages 265-280)
• Introduction to Algorithms by Cormen, ... (Computational Geometry Section)

Return to Top of Page

Area of a Polygon

• assume you have N points
• area = (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃y₂ ... + x_n*y₁ - x₁-y_n) / 2

Return to Top of Page

Equation of a Line

What is equation for a line given 2 points?

Given 2 points: (x1,y1) (x2,y2)

if (x1 == x2) 
 then
   line is vertical and slope is undefined
   x = x1
 else
   m = (y2 - y1) / (x2 - x1)
   b = y2 - m*x2
   y = m*x + b ==> y = ((y2-y1)/(x2-x1))*x + (y2 - ((y2-y1)/(x2-x1))*x2)
fi

What is equation of a line given a point and the slope?

Given a slope and a point: m (x1, y1)
  b = y1 - m*x1
  y = m*x + b ==> y = m*x + y1 - m*x1

Return to Top of Page

Is a point on a line?

Given a line and a point: y = mx + b  (x1,y1)

if (y1 == (m*x1 + b))
 then
   the point is on the line
 else
   if (y1 < (m*x1 + b))
    then
      the point is below the line
    else
      the point is above the line
   fi
fi

Return to Top of Page

Given two lines, what is their intersection point?

Given two lines: y = m1*x + b1  y = m2*x + b2

If the lines have the same slopes, they do not intersect unless they are the same line.

if (m1 == m2)
 then
   if (b1 == b2)
    then
      they are same line -- they intersect at all points
    else
      they have same slope but do not ever intersect
    fi
 else
   m1*x + b1 = m2*x + b2
   m1*x - m2*x = b2 - b1
   (m1 - m2) * x = b2 - b1
   x = (b2 - b1) / (m1 - m2)
   y = m1*x + b1
fi

Return to Top of Page

Intersection of a Line and a Circle

Return to Top of Page