convex_hull.cpp

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const int N = 100000;

inline double square(double x) {
  return x * x;
}

struct point {
  int x, y;

  inline int cross(const point &p1, const point &p2) const {
    return (p1.x - x) * (p2.y - y) + (p2.x - x) * (p1.y - y);
  }

  inline bool operator< (const point &that) const {
    return x < that.x;
  }

  inline double distance(const point &that) {
    return sqrt(square(x - that.x) + square(y - that.y));
  }
};

class stack {
  int head;
  point data[N];

public:
  stack() : head(-1) { }

  inline void push(const point &pt) {
    data[++head] = pt;
  }

  inline void pop() {
    --head;
  }

  inline const point &top() const {
    return data[head];
  }

  inline const point &under_top() const {
    return data[head - 1];
  }

  double distance() {
    double sum = 0.0;
    for (int i = 0; i < head; i++)
      sum += data[i].distance(data[i + 1]);
    return sum;
  }
};

int n;
point pts[N];
stack up, down;

int main() {
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> pts[i].x >> pts[i].y;

  sort(pts, pts + n); // sort points by x-coordinate

  // go upwards
  up.push(pts[0]);
  up.push(pts[1]);
  for (int i = 2; i < n; i++) {
    if (up.under_top().cross(up.top(), pts[i]) < 0)
      up.pop();

    up.push(pts[i]);
  }

  // go downwards
  down.push(pts[0]);
  down.push(pts[1]);
  for (int i = 2; i < n; i++) {
    if (down.under_top().cross(down.top(), pts[i]) > 0)
      down.pop();

    down.push(pts[i]);
  }

  // compute
  double ans = up.distance();
  
  cout << ans << endl;
  
  ans += down.distance();

  cout << setprecision(2) << ans << endl;
  
  cin.get(); cin.get();

  return 0;
}

修改退栈方式。