Z_Michael

1185

Jun 10th, 2020
694
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <stack>
  5. #define _USE_MATH_DEFINES
  6. #include <math.h>
  7. using namespace std;
  8.  
  9. struct coor {
  10.     long long int x, y;
  11. };
  12.  
  13. long long int rotate(coor a, coor b, coor c) {
  14.     return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
  15. }
  16.  
  17. vector <coor> dots;
  18.  
  19. int n;
  20. double l;
  21.  
  22. int main()
  23. {
  24.     cin >> n >> l;
  25.  
  26.     for (int i = 0; i < n; i++) {
  27.  
  28.         int a, b;
  29.         cin >> a >> b;
  30.  
  31.         dots.push_back({ a, b });
  32.     }
  33.  
  34.  
  35.     int yy = 100000000, ind = -1;;
  36.     for (int i = 0; i < n; i++) {
  37.         if (dots[i].y < yy) {
  38.             yy = dots[i].y;
  39.             ind = i;
  40.         }
  41.     }
  42.  
  43.     coor beg = dots[ind];
  44.     dots.erase(dots.begin() + ind);
  45.  
  46.     for (int i = 0; i < n - 1; i++) {
  47.         dots[i].x = dots[i].x - beg.x;
  48.         dots[i].y = dots[i].y - beg.y;
  49.     }
  50.  
  51.     beg.x = 0; beg.y = 0;
  52.  
  53.     sort(dots.begin(), dots.end(), [](coor a, coor b) {
  54.         if (a.x * b.y == b.x * a.y) {
  55.             if (a.y == b.y) {
  56.                 if (a.x < b.x) {
  57.                     return true;
  58.                 }
  59.                 else {
  60.                     return false;
  61.                 }
  62.             }
  63.             else {
  64.                 if (a.y < b.y) {
  65.                     return true;
  66.                 }
  67.                 else {
  68.                     return false;
  69.                 }
  70.             }
  71.         }
  72.         else {
  73.             return (a.x * b.y > b.x * a.y);
  74.         }
  75.     });
  76.  
  77.     vector <coor> aga;
  78.  
  79.     aga.push_back(beg);
  80.     aga.push_back(dots[0]);
  81.  
  82.     for (int i = 1; i < n - 1; i++) {
  83.  
  84.         while (rotate(aga[aga.size() - 1], dots[i], aga[aga.size() - 2]) < 0) {
  85.             aga.erase(aga.end() - 1);
  86.         }
  87.  
  88.         aga.push_back(dots[i]);
  89.     }
  90.  
  91.     while (rotate(aga[aga.size() - 1], beg, aga[aga.size() - 2]) < 0) {
  92.         aga.erase(aga.end() - 1);
  93.     }
  94.    
  95.     double summ = 0;
  96.     for (int i = 1; i < aga.size(); i++) {
  97.         summ += sqrt(pow(aga[i].x - aga[i - 1].x, 2) + pow(aga[i].y - aga[i - 1].y, 2));
  98.     }
  99.  
  100.     summ += sqrt(pow(beg.x - aga[aga.size() - 1].x, 2) + pow(beg.y - aga[aga.size() - 1].y, 2));
  101.  
  102.     summ += 2 * M_PI * l;
  103.  
  104.     cout << (int) (summ + 0.5);
  105. }
Advertisement
Add Comment
Please, Sign In to add comment