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
• Points clockwise, colinear or countr clockwise

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

Points clockwise, colinear or countr clockwise

Consider two points: P₁, P₂. If you consider these points as vectors anchored at the origin, the P₂ must be counter clockwise, colinear or clockwise of P₁. Two questions should spring to your mind:

1. Why do we care?
2. How do we figure it out?

The why is because it is useful for numerouse reasons (some of which will be shown shortly).

The how is a lot easier than it might seem. You use cross product:

  (X1 * Y2) - (X2 * Y1)    

• If the result is positive, then P₂ is counter-clockwise of P₁.
• If the result is zero, then P₂ is colinear with P₁.
• If the result is negative, then P₂ is clockwise of P₁.

1. (0, 0)
2. P₁
3. P₁ + P₂
4. P₂

One really useful place for this is in finding the smallest (in area) convex polygon that contains all the points in a list.

Return to Top of Page