UVa 11626 - Convex Hull

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct P {

  P (long long x, long long y) : x(x), y(y) {
  }

  bool operator < (const P & other) const {
    return x != other.x ? x < other.x : y < other.y;
  }

  P operator - (const P & other) const {
    return P(x - other.x, y - other.y);  
  }

  long long operator ^ (const P & other) const {
    return x * other.y - y * other.x;
  }

  long long x, y;
};

int orient(P & p1, P & p2, P & p3) {
  long long area = (p2 - p1) ^ (p3 - p1);
  return area == 0 ? 0 : area > 0 ? 1 : -1;
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    vector<P> points;
    while (N--) {
      long long x, y;
      char temp[99];
      scanf("%lld%lld%s", &x, &y, temp);
      points.push_back(P(x, y));
    }
    sort(points.begin(), points.end());
    vector<P> ch[2];
    ch[0].push_back(points[0]);
    ch[0].push_back(points[1]);
    for (int i = 2; i < points.size(); i++) {
      ch[0].push_back(points[i]);
      while (ch[0].size() >= 3 && orient(points[i], ch[0][ch[0].size() - 2], ch[0][ch[0].size() - 3]) > 0) {
        ch[0].pop_back();
        ch[0].pop_back();
        ch[0].push_back(points[i]);
      }
    }
    ch[1].push_back(points[points.size() - 1]);
    ch[1].push_back(points[points.size() - 2]);
    for (int i = points.size() - 3; i >= 0; i--) {
      ch[1].push_back(points[i]);
      while (ch[1].size() >= 3 && orient(points[i], ch[1][ch[1].size() - 2], ch[1][ch[1].size() - 3]) > 0) {
        ch[1].pop_back();
        ch[1].pop_back();
        ch[1].push_back(points[i]);
      }
    }
    vector<P> ans;
    for (int i = 0; i < ch[0].size(); i++) {
      ans.push_back(ch[0][i]);
    }
    for (int i = 1; i < ch[1].size() - 1; i++) {
      ans.push_back(ch[1][i]);
    }
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
      printf("%lld %lld\n", ans[i].x, ans[i].y);
    }
  }
  return 0;
}