Opis glavnog rešenja

Da bismo izračunali obim konveksnog omotača, dovoljno je da pronađemo temena omotača u redosledu kojim se obilaze po njegovoj granici, a zatim da saberemo dužine susednih stranica. U ovom rešenju koristi se Jarvisov algoritam, poznat i kao algoritam uvijanja poklona (gift wrapping). Ideja je da u svakom koraku iz trenutnog temena izaberemo ono sledeće teme tako da sve ostale tačke ostanu sa iste strane prave određene tom stranicom.

Algoritam najpre pronalazi najlevlju tačku, tj. tačku sa najmanjom \(x\) koordinatom. Ona sigurno pripada konveksnom omotaču, pa od nje možemo započeti obilazak. Neka je trenutna tačka \(p\). Kao privremenog kandidata za sledeće teme uzimamo neku drugu tačku \(q\), a zatim prolazimo kroz sve tačke skupa. Ako za neku tačku \(i\) važi da je trojka \((p, i, q)\) orijentisana suprotno od trenutnog izbora, onda je tačka \(i\) bolji kandidat za sledeće teme omotača i postavljamo \(q = i\).

Orijentacija tri tačke računa se pomoću vektorskog proizvoda. Njegov znak govori da li se pri prelasku iz prve tačke ka drugoj, pa ka trećoj, skreće ulevo, udesno ili su tačke kolinearne. Na taj način se bez računanja uglova pronalazi sledeća stranica konveksnog omotača.

Kada se odredi sledeće teme \(q\), dužina stranice između trenutne tačke \(p\) i tačke \(q\) dodaje se na rezultat. Zatim se obilazak nastavlja iz tačke \(q\). Postupak se završava kada se ponovo stigne do početne najlevlje tačke. Tada su sve stranice konveksnog omotača obiđene, a sabrana vrednost predstavlja njegov obim.

Ako je \(h\) broj temena konveksnog omotača, u svakom od tih \(h\) koraka obilazi se svih \(N\) tačaka. Zato je vremenska složenost algoritma \(O(Nh)\), što je u najgorem slučaju \(O(N^2)\). Memorijska složenost je \(O(N)\), jer se čuva niz učitanih tačaka.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point {  
   int x;
   int y;
};


int orientation(Point p, Point q, Point r)

{
   int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

   if (val == 0)
      return 0; 

   return (val > 0) ? 1 : 2; 

}

float dist(Point p, Point q){
   return sqrt((p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y));
}

// Algoritam uvijanja poklona
float convexHull(vector<Point> &points, int n) {

   // Nema dovoljno tačaka za omotač
   if (n < 3)
      return 0;

   int l = 0;
   
   // Pamtimo indeks tačke sa najmanjom x koordinatom. Ona se mora naći
   // u konveksnom omotaču
   for (int i = 1; i < n; i++)
      if (points[i].x < points[l].x)
         l = i;

   int p = l, q;
   float res = 0;

   do {
          // Biramo tačku koja je kandidat za dodavanje u konveksni omotač
      q = (p + 1) % n;

          // Tražimo boljeg kandidata među preostalim tačkama proverom  orijentacije
          // poslednje dodate tačke (p), kandidata (q) i tekuće tačke (i)
      for (int i = 0; i < n; i++)

            if (orientation(points[p], points[q], points[i]) == 2)
               q = i;

          // Kada se petlja završi, sigurni smo da je q pravi kandidat
          // i dodajemo ga u konveksni omotač
      res += dist(points[p], points[q]);

      p = q; 

        // Petlja se završava kada pokušamo da dodamo polaznu tačku u omotač
   } while (p != l);

   return res;

}

int main() {
   int N;
   cin >> N;

   vector<Point> points(N);

   for(int i = 0; i < N; i++)
      cin >> points[i].x >> points[i].y;
   

   cout << convexHull(points, N) << endl;

   return 0;

}