Clasele 11-12 lecția 1 - 18 sep 2015

From Algopedia
Jump to navigationJump to search

Punctul

Reprezentare în memoria calculatorului

Vom stoca coordonatele carteziene ale punctului (ordonata - x și abscisa - y).

struct Punct {
  double x;
  double y;
};

Distanța dintre două puncte

Vom folosi teorema lui Pitagora și vom obține formula:

double distanta(Punct p1, Punct p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) +
      (p1.y - p2.y) * (p1.y - p2.y));
}

Dreapta

O dreaptă este unic determinată de două ouncte distincte. Pe baza coordonatelor celor două puncte putem determina ecuația dreptei.

Ecuația dreptei

Ecuația dreptei este o egalitate în care apar două necunoscute (x și y) cu proprietatea că mulțimea soluțiilor perechilor de numere (x, y) coincide cu coordonatele tuturor punctelor de pe dreaptă.

Ecuația dreptei determinată de două puncte

Se dau două puncte p1 și p2 de coorodonate (x1, y1) și (x2, y2). Fie (x, y) un punct de pe dreapta determinată în mod unic de punctele p1 și p2. Atunci, folosind asemănarea triunghiurilor obținem ecuația:

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)

(x - x1) * (y2 - y1) = (y - y1) * (x2 - x1)

x * y2 - x * y1 - x1 * y2 + x1 * y1 = y * x2 - y * x1 - y1 * x2 + y1 * x1

x * y2 - x * y1 - x1 * y2 + x1 * y1 - y * x2 + y * x1 + y1 * x2 - y1 * x1 = 0

x * (y2 - y1) + y * (x1 - x2) + y1 * x2 - x1 * y2 = 0

Introducând substituțiile:

a = y2 - y1
b = x1 - x2
c = y1 * x2 - x1 * y2

ajungem la forma generală a ecuației dreptei:

a*x + b*y + c = 0

Reprezentarea în memoria calculatorului

Vom stoca o dreaptă prin valoarea coeficienților a, b și c ale ecuației sale:

struct Dreapta {
  double a;
  double b;
  double c;
};

Pe care le vom calcula astfel:

Dreapta obtineDreapta(Punct p1, Punct p2) {
  Dreapta d;
  d.a = p2.y - p1.y;
  d.b = p1.x - p2.x;
  d.c = p1.y * p2.x - p1.x * p2.y;
  return d;
}

Interpretarea ecuației dreptei

Pentru a testa dacă un punct p aparține unei drepte d, înlocuim x și y din ecuația dreptei cu coordonatele punctului p.

bool egale(double a, double b) {
  return 1 - 1e-8 <= a / b && a / b <= 1 + 1e-8;
}

bool punctApartineDreptei(Dreapta d, Punct p) {
  return egale(d.a * p.x + d.b * p.y + d.c, 0);
}

Semiplanele determinate de o dreaptă

Orice drepată d (cu ceficienții a, b și c) împarte planul în două semiplane. Vom distinge între ele numindu-le semiplanul pozitiv și semiplanul negativ.

Putem determina dacă un punct p (de coordonate x și y) se află în semiplanul pozitiv sau în semiplanul negativ calculând semnul expresiei:

a*x + b*y + c

astfel:

int semiplan(Dreapta d, Punct p) {
  if (egale(d.a * p.x + d.b * p.y + d.c, 0)) {
    return 0;
  } else if (d.a * p.x + d.b * p.y + d.c < 0) {
    return -1;
  } else {
    return 1;
  }
}

Forma canonică a ecuației dreptei

Ecuația unei drepe d poate fi înmulțită cu orice număr real r diferit de 0 și astfel obținem o altă ecuație cu aceeași mulțime a soluțiilor. Altfel spus, înmulțind coeficienții ecuației dreptei (a, b și c) cu același număr rear r obținem coeficienții unei ecuații ce desemnează aceeași dreaptă d.

De aceea, dacă pentru coeficienții a, b și c ai unei drepte d alegem r astfel:

r = 1 / sqrt(a * a + b * b)

și îi înmulțim prin r, aceștia vor respecta condiția suplimentară:

a * a + b * b = 1

Putem aduce o dreaptă la forma sa canonică astfel:

Dreapta obtineFormaCanonica(Dreapta d) {
  double r = sqrt(d.a * d.a + d.b * d.b);
  d.a /= r;
  d.b /= r;
  d.c /= r;
  return d;
}

Coincidența a două drepte

Două drepte coincid dacă și numai dacă conțin aceleași puncte. Două drepete conțin aceleași puncte dacă și numai dacă soluțiile ecuațiilor lor coincid. Soluțiile a două ecuații coincid dacă și numai dacă sunt echivalente. Două ecuații sunt echivalente dacă și numai dacă înmulțind una dintre ele cu un număr real r o obținem pe cealaltă.

Astfel, pentru a verifica dacă două drepte d1 și d2 cu coeficienții a1, b1, c1 respectiv a2, b2, și c2 coincid este suficient să verificăm dacă:

a1 / a2 = b1 / b2 = c1 / c2

Mai mult, dacă cele două ecuații sunt în formă canonică atunci:

a1 / a2 = b1 / b2 = c1 / c2 = 1 sau -1

iar semnul raportului dă "sensul" dreptei, care determină semnele semiplanelor.

Putem verifica dacă două drepte coincid astfel:

bool coincid(Dreapta d1, Dreapta d2) {
  return egale(d1.a * d2.b, d1.b * d2.a) &&
      egale(d1.a * d2.c, d1.c * d2.a);
}

Panta unei drepte

Fie două puncte p1 și p2 de coordonate x1 și y1 respectiv x2 și y2 aparținând unei drepte d. Spunem că panta m dreptei d este:

m = (y2 - y1) / (x2 - x1)

Folosind formulele de calcul ale coeficienților a și b:

a = y2 - y1
b = x1 - x2

putem deduce că:

m = -a / b

Putem calcula panta unei drepte astfel:

double panta(Dreapta d) {
  return -d.a / d.b;
}

Paralelismul a două drepte

Două drepte d1 și d2 cu coeficieții a1, b1 și c1 respectiv a2, b2 și c2 sunt paralele dacă au aceeași pantă, adică:

-a1 / b1 = -a2 / b2

a1 / b1 = a2 / b2

a1 * b2 = a2 * b1

Putem verifica dacă două drepte sunt paralele astfel:

bool suntParalele(Dreapta d1, Dreapta d2) {
  return egale(d1.a * d2.b, d2.a * d1.b);
}

Distanța de la un punct la o dreaptă

Fie d o dreaptă cu coeficienții ecuației în formă canonică a, b și c și p un punct de coordonate x și y.

Distanța de la punctul p la dreapta d este dată de formula:

a*x + b*y + c

Putem calcula distanța de la un punct la o dreaptă astfel:

double distanta(Dreapta d, Punct p) {
  return d.a * p.x + d.b * p.y + d.c;
}

Triunghiul

Reprezentarea în memoria calculatorului

Vom stoca un triunghi prin cele trei puncte care îl determină:

struct Triunghi {
  Punct A;
  Punct B;
  Punct C;
};

Calculul ariei (cu formula lui Heron)

Formula lui Heron pentru calculul ariei unui triunghi cu vârfurile A, B și C este:

a = BC
b = AC
c = AB
p = (a + b + c) / 2
Aria = sqrt((p - a) * (p - b) * (p - c) * p)

Putem calcula aria folosind formula lui Heron astfel:

double ariaHeron(Triunghi t) {
  double a = distanta(t.B, t.C);
  double b = distanta(t.A, t.C);
  double c = distanta(t.A, t.B);
  double p = (a + b + c) / 2;
  return sqrt((p - a) * (p - b) * (p - c) * p);
}

Calculul ariei (cu determinant)

Formula de calcul a ariei unui triunghi cu vârfurile A, B și C cu ajutorul unui determinant este:

    | A.x A.y 1 |
D = | B.x B.y 1 |
    | C.x C.y 1 |
Aria = |D| / 2

Putem calcula aria cu ajutorul determinantului astfel:

double ariaDeterminant(Triunghi t) {
  double D
      = t.A.x * t.B.y
      + t.B.x * t.C.y
      + t.C.x * t.A.y
      - t.C.x * t.B.y
      - t.A.x * t.C.y
      - t.B.x * t.A.y;
  return fabs(D) / 2;
}

Calculul ariei (cu înălțimea)

Formula pentru calculul ariei unui triunghi cu vârfurile A, B și C cu ajutorul înălțimii este:

Aria = AB * dist(C, AB) / 2

Putem calcula aria cu ajutorul înățimii astfel:

double ariaInaltime(Triunghi t) {
  return distanta(t.A, t.B) * distanta(obtineFormaCanonica(obtineDreapta(t.A, t.B)), t.C);
}

Sensul punctelor unui triunghi

Cele trei puncte ale unui triunghi pot fi date în sens trigonometric sau în sensul acelor de ceasornic.

Putem determina sensul în care sunt date în două feluri:

  • cu semnul determinantului;
  • cu semnul semiplanului mărginit de dreapta formată de primele două puncte și care îl conține pe al treilea.

Putem afla sensul punctelor unui triunghi astefel:

int sensTriunghi(Triunghi t) {
  double D
      = t.A.x * t.B.y
      + t.B.x * t.C.y
      + t.C.x * t.A.y
      - t.C.x * t.B.y
      - t.A.x * t.C.y
      - t.B.x * t.A.y;
  if (D < 0) {
    return -1;
  } else {
    return 1;
  }
}

Temă

Pentru data viitoare nu veți avea temă.