Objectives

• Know some of the basic formulae for
  • Circles
  • Triangles
  • Squares
• Most code samples from Competitive Programming 3.

Circles: Testing if Inside

• For a circle, you need a center $(a,b)$ and a radius $r$.
• All points $(x-a)+(y-b)=r^2$

int insideCircle(point_i p, point_i c, int r) { // all integer version
   int dx = p.x - c.x, dy = p.y - c.y;
   int Euc = dx * dx + dy * dy, rSq = r * r;
    // all integer
   return Euc < rSq ? 0 : Euc == rSq ? 1 : 2;
   // 0 = inside, 1 = on border, 2 = outside
}

Basic Formulae

• Value of $\pi$ is acos(-1.0){.verbatim}
• Diameter $d=2r$
• Circumference is $2\pi r$, area is $\pi r^2$
• Given two points p1{.verbatim} and p2{.verbatim} and radius r{.verbatim}, we can compute the circles:

bool circle2PtsRad(point p1, point p2, double r, point &c) {
   double d2 = (p1.x - p2.x) * (p1.x - p2.x) +
               (p1.y - p2.y) * (p1.y - p2.y);
   double det = r * r / d2 - 0.25;
   if (det < 0.0) return false;
   double h = sqrt(det);
   c.x = (p1.x + p2.x) * 0.5 + (p1.y - p2.y) * h;
   c.y = (p1.y + p2.y) * 0.5 + (p2.x - p1.x) * h;
   return true;
}

Triangles: Types

• Types of triangles:

  Equilateral : All three sides the same, all angles are 60 degrees

  Isosceles : Two edges the same, two degrees the same.

  Scalene : All edges different

  Right : One angle 90 degrees

Area Calculations

Given : sides $a,b,c$

Perimeter : $p=a+b+c,s=\frac{p}{2}$

Area : $\sqrt{s(s-a)(s-b)(s-c)}$

Circles

• Triangle contain an inscribed cirlce:

double rInCircle(double ab, double bc, double ca) {
   return area(ab, bc, ca) / (0.5 * perimeter(ab, bc, ca)); }
double rInCircle(point a, point b, point c) {
   return rInCircle(dist(a, b), dist(b, c), dist(c, a)); }
int inCircle(point p1, point p2, point p3, point &ctr, double &r) {
   r = rInCircle(p1, p2, p3);
   if (fabs(r) < EPS) return 0; // no inCircle center
   line l1, l2; // compute these two angle bisectors
   double ratio = dist(p1, p2) / dist(p1, p3);
   point p = translate(p2, scale(toVec(p2, p3), ratio / (1 + ratio)));
   pointsToLine(p1, p, l1);
   ratio = dist(p2, p1) / dist(p2, p3);
   p = translate(p1, scale(toVec(p1, p3), ratio / (1 + ratio)));
   pointsToLine(p2, p, l2);
   areIntersect(l1, l2, ctr);
   return 1; }

Circumscribed Circles

• Triangle can be enclosed by an circumscribed cirlce:
• Radius is $R=a\ast b\ast c/(4\ast area(a,b,c)$

    double rCircumCircle(double ab, double bc, double ca) {
       return ab * bc * ca / (4.0 * area(ab, bc, ca)); }
    double rCircumCircle(point a, point b, point c) {
       return rCircumCircle(dist(a, b), dist(b, c), dist(c, a)); }

Trigonometrics

Is a triangle possible? : $a+b>c$, where $c$ is largest side.

Pythagorean Theorem : $a+b=c$

Law of Sines : $\frac{a}{sin(\alpha )}=\frac{b}{sin(\beta )}=\frac{c}{sin(\gamma )}=2R$

Law of Cosines : $c^2=a+b^2-2\times a\times b\times cos(\gamma )$