Advertisement
juaniisuar

Untitled

Oct 23rd, 2018
864
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cmath>
  5. #include <map>
  6. #include <iomanip>
  7.  
  8. #define pb push_back
  9. #define fst first
  10. #define snd second
  11.  
  12. #define forn(i,n) forr(i,0,n)
  13. #define forr(i,x,n) for(int i=(x); i<int(n); i++)
  14.  
  15. using namespace std;
  16.  
  17. typedef unsigned long long ll;
  18.  
  19. const ll MAXN = 200005;
  20. const ll INF = 1e18;
  21. const ll MOD = 1e9 + 7;
  22.  
  23. struct pt {
  24. double x, y;
  25. int id;
  26.  
  27. pt(double x=0, double y=0, int id=0):x(x),y(y),id(id){}
  28. pt operator-(pt a){return pt(x-a.x, y-a.y);}
  29. double norm(){return sqrt(x*x+y*y);}
  30. };
  31. double dist(pt a, pt b){return (b-a).norm();}
  32.  
  33. bool cmp (pt a, pt b) {
  34. return a.x <b.x || a.x == b.x && a.y <b.y;
  35. }
  36.  
  37. bool cw (pt a, pt b, pt c) {
  38. return a.x * (b.y-c.y) + b.x * (c.y-a.y) + c.x * (a.y-b.y) <0;
  39. }
  40.  
  41. bool ccw (pt a, pt b, pt c) {
  42. return a.x * (b.y-c.y) + b.x * (c.y-a.y) + c.x * (a.y-b.y)> 0;
  43. }
  44.  
  45. void convex_hull (vector <pt> & a) {
  46. if (a.size () == 1) return;
  47. sort (a.begin (), a.end (), & cmp);
  48. pt p1 = a [0], p2 = a.back ();
  49. vector <pt> up, down;
  50. up.push_back (p1);
  51. down.push_back (p1);
  52. for (size_t i = 1; i <a.size (); ++ i) {
  53. if (i == a.size () - 1 || cw (p1, a [i], p2)) {
  54. while (up.size () >= 2 &&! cw (up [up.size () - 2], up [up.size () - 1], a [i]))
  55. up.pop_back ();
  56. up.push_back (a [i]);
  57. }
  58. if (i == a.size () - 1 || ccw (p1, a [i], p2)) {
  59. while (down.size () >= 2 &&! ccw (down [down.size () - 2], down [down.size () - 1], a [i]))
  60. down.pop_back ();
  61. down.push_back (a [i]);
  62. }
  63. }
  64. a.clear ();
  65. for (size_t i = 0; i <up.size (); ++ i)
  66. a.push_back (up [i]);
  67. for (size_t i = down.size () - 2; i> 0; --i)
  68. a.push_back (down [i]);
  69. }
  70.  
  71. int N;
  72. vector<pt> V;
  73.  
  74. int main(){
  75. ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  76.  
  77. cin >> N;
  78. forn(i,N){
  79. double a, b;
  80. cin >> a >> b;
  81. V.push_back({a,b,i});
  82. }
  83.  
  84. convex_hull(V);
  85.  
  86. double perim = 0;
  87. forn(i, V.size()) perim += dist(V[i], V[(i+1)%V.size()]);
  88.  
  89. cout << fixed << setprecision(0) << perim << '\n';
  90.  
  91. return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement