Advertisement
Guest User

Untitled

a guest
Jun 17th, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Point {
  5.     long long  x, y;
  6.     Point() {}
  7.     Point(long long  _x, long long  _y) : x(_x), y(_y) {}
  8.     bool operator<(Point &b) {
  9.         return (this->x == b.x ? this->y < b.y : this->x < b.x);
  10.     }
  11. };
  12.  
  13. bool rightturn(Point pA, Point pB, Point pC) {
  14.     return (long long)pA.x * (pB.y - pC.y) + pB.x * (pC.y - pA.y) + pC.x * (pA.y - pB.y) < 0;
  15. }
  16.  
  17. bool leftturn(Point pA, Point pB, Point pC) {
  18.     return (long long)pA.x * (pB.y - pC.y) + pB.x * (pC.y - pA.y) + pC.x * (pA.y - pB.y) > 0;
  19. }
  20.  
  21. void ch(vector <Point> &in) {
  22.     sort(in.begin(), in.end());
  23.     Point first_point = in[0];
  24.     Point second_point = in.back();
  25.     vector <Point> convexhullup, convexhulldown;
  26.     convexhullup.push_back(first_point);
  27.     convexhulldown.push_back(first_point);
  28.     for (long long  i = 1; i < in.size(); ++i) {
  29.         if (i == in.size() - 1 || rightturn(first_point, in[i], second_point)) {
  30.             while (convexhullup.size() >= 2 && !rightturn(convexhullup[convexhullup.size() - 2], convexhullup[convexhullup.size() - 1], in[i])) convexhullup.pop_back();
  31.             convexhullup.push_back(in[i]);
  32.         }
  33.         if (i == in.size() - 1 || leftturn(first_point, in[i], second_point)) {
  34.             while (convexhulldown.size() >= 2 && !leftturn(convexhulldown[convexhulldown.size() - 2], convexhulldown[convexhulldown.size() - 1], in[i])) convexhulldown.pop_back();
  35.             convexhulldown.push_back(in[i]);
  36.         }
  37.     }
  38.     in.clear();
  39.     for (long long  i = 0; i < convexhullup.size(); ++i) in.push_back(convexhullup[i]);
  40.     for (long long  i = convexhulldown.size() - 2; i > 0; --i) in.push_back(convexhulldown[i]);
  41. }
  42.  
  43. int  main() {
  44.     long long  a, b;
  45.     int  n, l;
  46.     cin >> n >> l;
  47.     vector < Point > v;
  48.     for (long long  i = 0; i < n; i++) {
  49.         cin >> a >> b;
  50.         v.push_back({a, b});
  51.     }
  52.     ch(v);
  53.     double p = 0.0;
  54.     for (int i = 0; i < v.size(); i++) {
  55.         if (!i) {
  56.             p += sqrtl((v[0].x - v.back().x) * (v[0].x - v.back().x) + (v[0].y - v.back().y) * (v[0].y - v.back().y));
  57.         } else {
  58.             p += sqrtl((v[i].x - v[i - 1].x) * (v[i].x - v[i - 1].x) + (v[i].y - v[i - 1].y) * (v[i].y - v[i - 1].y));
  59.         }
  60.     }
  61.     p += 2 * acosl(-1) * l;
  62.     cout << fixed << setprecision(12) << p;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement