leetcode-go/poj/1113.wall/main.cc

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1000;

struct Point {
  int x;
  int y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
  bool operator<(const Point& that) const {
    if (this->x == that.x) return this->y < that.y;
    return this->x < that.x;
  }
  Point operator-(const Point& that) const {
    return Point(this->x - that.x, this->y - that.y);
  }
  int operator^(const Point& that) const {
    return this->x * that.y - this->y * that.x;
  }
} point[N];

double dist(const Point& a, const Point& b) {
  int dx = a.x - b.x;
  int dy = a.y - b.y;
  return sqrt((double)dx * dx + dy * dy);
}

int main() {
  int n, l;
  scanf("%d %d", &n, &l);
  for (int i = 0; i < n; i++) scanf("%d %d", &point[i].x, &point[i].y);
  sort(point, point + n);
  vector<Point> stack;
  stack.push_back(point[0]);
  stack.push_back(point[1]);
  for (int i = 2; i < n; i++) {
    Point& p = point[i];
    while (1 < stack.size()) {
      Point p1 = *(stack.end() - 1);
      Point p2 = *(stack.end() - 2);
      if (((p2 - p1) ^ (p - p2)) < 0)
        stack.pop_back();
      else
        break;
    }
    stack.push_back(p);
  }
  double len = 0.;
  Point pre = *(stack.begin());
  vector<Point>::iterator it;
  for (it = ++stack.begin(); it != stack.end(); ++it) {
    len += dist(pre, *it);
    pre = *it;
  }
  stack.clear();
  stack.push_back(point[n - 1]);
  stack.push_back(point[n - 2]);
  for (int i = n - 3; 0 <= i; i--) {
    Point& p = point[i];
    while (1 < stack.size()) {
      Point p1 = *(stack.end() - 1);
      Point p2 = *(stack.end() - 2);
      if (((p2 - p1) ^ (p - p2)) < 0)
        stack.pop_back();
      else
        break;
    }
    stack.push_back(p);
  }
  pre = *(stack.begin());
  for (it = ++stack.begin(); it != stack.end(); ++it) {
    len += dist(pre, *it);
    pre = *it;
  }
  printf("%.0lf\n", len + acos(-1.) * l * 2);
  return 0;
}