obim_omotaca

Neka je dato \(N\) tačaka u ravni. Izračunati obim njihovog konveksnog omotača.

Opis ulaza

Sa standardnog ulaza se učitava broj tačaka \(N\) (\(3 <= N <= 10^4\)), a zatim u sledećih \(N\) linija i koordinate \(x_i\) \(y_i\) \(i\)-te tačke.

Opis izlaza

Na standardni izlaz ispisati obim konveksnog omotača datog skupa tačaka.

Primer

Ulaz

6    
1 1    
2 5    
3 3    
5 3    
3 2    
2 2

Izlaz

12.2

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#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));
}

float convexHull(vector<Point> &points, int n) {

   if (n < 3)
      return 0;

   int l = 0;

   for (int i = 1; i < n; i++)
      if (points[i].x < points[l].x)
         l = i;

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

   do {
      q = (p + 1) % n;

      for (int i = 0; i < n; i++)

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

      res += dist(points[p], points[q]);

      p = q; 

   } 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;

}