Zajęcia 9: jak to napisać? cz. 2, geometria

Geometria

struct pt {
   double x,y;
   pt() : x(0), y(0) { }
   pt(double x, double y) : x(x), y(y) { }
   bool operator<(const pt& a) const { return make_pair(x,y) < make_pair(a.x,a.y); }
};

pt operator+(const pt& a, const pt& b) { return pt(a.x+b.x, a.y+b.y); }
pt operator-(const pt& a, const pt& b) { return pt(a.x-b.x, a.y-b.y); }
pt operator*(const pt& a, double c) { return pt(a.x*c, a.y*c); }
pt operator/(const pt& a, double c) { return pt(a.x/c, a.y/c); }
double operator^(const pt& a, const pt& b) { return a.x*b.y - a.y*b.x; }
double len(const pt& a) { return sqrt(a.x*a.x + a.y*a.y); }
pt norm(const pt& a) { return a / len(a); }
pt rot90(const pt& a) { return pt(-a.y,a.x); }

Prosta styczna do dwóch okręgów

Mamy dwa okręgi (S,R), (s,r) i chcemy wyznaczyć proste styczne zewnętrznie i wewnętrznie do tych okręgów. Na początek styczne zewnętrznie, wyznaczmy punkt styczności dla okręgu (S,R). Dla uproszczenia ustalmy S = (0,0), s = (d,0) i wyznaczmy punkt (k,0) przecięcia stycznych. Z twierdzenia Talesa mamy k/R = (k-d)/r, zatem k = Rd/(R-r). Punkt styczności musi leżeć na okręgu (S,R) oraz na okręgu ((k/2,0), k/2), zatem x² + y² = R² oraz (x-k/2)² + y² = (k/2)². Podstawiając pierwsze równanie do drugiego dostajemy x = R²/k = R(R-r)/d, natomiast y = ±(R² - x²)^1/2.

W ogólnym przypadku dla okręgów (S,R), (s,r) jako d podstawiamy odległość między nimi i odpowiednio przesuwamy rozwiązanie:

void circle_extangent(pt& S, double R, pt& s, double r, pt& a, pt& b) {
   double d = len(s-S);
   double x = R*(R-r)/d;
   double y = sqrt(R*R-x*x);
   a = S + norm(s-S) * x + rot90(norm(s-S)) * y;
   b = S + norm(s-S) * x - rot90(norm(s-S)) * y;
}

Dla stycznych wewnętrznie mamy k/R = (d-k)/r, zatem k = Rd/(r+R), a dalej jest tak samo. Zauważmy, że dla r=0 dostajemy styczną do okręgu (S,R) przechodzącą przez punkt s.

Wypukła otoczka

vector<pt> hull(vector<pt> p) {
   int n = p.size(), se;
   if (n<=1) return p;
   vector<pt> ans;
   sort(p.begin(),p.end());
   pt s[n];

   REP(faza,2) {
      se = 0;
      REP(i,n) {
         while (se >= 2 && (p[i] - s[se-2] ^ s[se-1] - s[se-2]) <= 0)
            --se;
         s[se++] = p[i];
      }
      REP(i,se-1) ans.push_back(s[i]);
      reverse(p.begin(),p.end());
   }

   return ans;
}

Zadanie domowe

Zadanie domowe: zadanie Czworokąty wypukłe na ASD-SIO.

Jeśli ktoś potrzebuje wskazówki, znajdzie ją w tym IKO autorstwa Tomka Idziaszka.

Autor notatek: Tomasz Idziaszek.