Advertisement
osipyonok

Untitled

Jun 6th, 2016
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. Исходный код
  2. #include<bits/stdc++.h>
  3.  
  4. #define INF 1000010000
  5. #define nl '\n'
  6. #define pb push_back
  7. #define ppb pop_back
  8. #define mp make_pair
  9. #define fi first
  10. #define se second
  11. #define pii pair<int,int>
  12. #define pdd pair<double,double>
  13. #define all(c) (c).begin(), (c).end()
  14. #define SORT(c) sort(all(c))
  15. #define rep(i,n) for( int i = 0; i < n; ++i )
  16. #define repi(i,n) for( int i = 1 ; i <= n; ++i )
  17. #define repn(i,n) for( int i = n ; i > 0 ; --i )
  18. #define repf(j,i,n) for( int j = i ; j < n ; ++j )
  19. #define die(s) {std::cout << s << nl;}
  20. #define dier(s) {std::cout << s; return 0;}
  21. #define vi vector<int>
  22. typedef long long ll;
  23.  
  24. using namespace std;
  25.  
  26. struct point
  27. {
  28. int x,y;
  29. inline point(int _x,int _y){
  30. x=_x;
  31. y=_y;
  32. }
  33. };
  34.  
  35. inline bool cmp(point a,point b){
  36. return a.x < b.x || a.x==b.x && a.y < b.y;
  37. }
  38.  
  39. inline bool cw(point a,point b,point c){
  40. return ((a.x - b.x) * (c.y - b.y) - (c.x - b.x) * (a.y - b.y)) < 0;
  41. }
  42.  
  43. inline bool ccw(point a,point b,point c){
  44. return ((a.x - b.x) * (c.y - b.y) - (c.x - b.x) * (a.y - b.y)) > 0;
  45. }
  46.  
  47. inline double dist(point a,point b){
  48. return sqrt(double((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
  49. }
  50.  
  51. int main() {
  52. ios_base::sync_with_stdio(false);
  53. cin.tie(NULL);
  54. // cout.precision(1);
  55. vector<point> v;
  56. int n;
  57. cin >> n;
  58. int x , y;
  59. rep(i , n){
  60. cin >> x >> y;
  61. v.pb(point(x , y));
  62. }
  63. sort(all(v) , cmp);
  64. vector<point> up , down;
  65. point p1 = v[0] , p2=v.back();
  66. double ans = 0;
  67. up.pb(p1);
  68. down.pb(p1);
  69. repf(i , 1 , v.size() ){
  70. if(i == v.size() - 1 || cw(p1 , v[i] , p2)){
  71. while(up.size() > 1 && !cw(up[up.size() - 2] , up[up.size() - 1] , v[i])) up.ppb();
  72. up.pb(v[i]);
  73. }
  74. if(i == v.size() - 1 || ccw(p1 , v[i] , p2)){
  75. while(down.size() > 1 && !ccw(down[down.size() - 2] , down[down.size() - 1] , v[i])) down.ppb();
  76. down.pb(v[i]);
  77. }
  78. }
  79. v.clear();
  80. rep(i , up.size()) v.pb(up[i]);
  81. repn(i , down.size() - 2) v.pb(down[i]);
  82. v.pb(v[0]);
  83. rep(i , v.size() - 1) ans += dist(v[i] , v[i+1]);
  84. printf("%.1lf\n", ans);
  85. return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement