587. Erect the Fence

typedef int T;
#define all(v)          v.begin(), v.end()
#define unq(v)          sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define pb              push_back
struct PT{
    T x, y;

    PT(){}
    PT(T x, T y) : x(x), y(y) {}
    inline bool operator == (const PT &p) const {
        return x == p.x && y == p.y;
    }
    inline bool operator < (const PT &p) const {
        return ((x < p.x) || (x == p.x && y < p.y));
    }
}_f;

const double eps = 1e-9;

inline PT operator - (const PT &u, const PT &v) {
    return PT(u.x - v.x, u.y - v.y);
}
T sqnorm(const PT &u) {
    return (u.x * u.x) + (u.y * u.y);
}
/* line ab to point c */
int orientation(const PT &a, const PT &b, const PT &c) {
    T val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if(abs(val) < eps) return 0;      // 0 linear
    return val > eps ? 1 : -1;    // + ccw, - acw
}
bool AClockCmp(const PT &a, const PT &b){
    int val = orientation(_f, a, b);
    if(val == 0) return sqnorm(a - _f) < sqnorm(b - _f);
    return val < 0;
}
vector< PT > GrahamScan(vector< PT >& v){
    if(v.size() < 3) return v;
    _f = v[0];
    int pivot = 0;
    for(int i=1; i<v.size(); i++){
        if(v[i].y < _f.y) _f = v[i], pivot = i;
        else if(v[i].y == _f.y && v[i].x < _f.x) _f = v[i], pivot = i;
    }
    swap(v[0], v[pivot]);
    sort(v.begin()+1, v.end(), AClockCmp);
    vector< PT > hull;
    hull.pb(v[0]); hull.pb(v[1]);
    for(int i=2; i<v.size(); i++){
        while(hull.size() > 1 && orientation(hull[hull.size()-2], hull.back(), v[i]) > 0) hull.pop_back();
        hull.pb(v[i]);
    }
    for(int i=v.size()-2; i>=0; i--){
        if(orientation(hull.back(), hull[0], v[i]) == 0) hull.pb(v[i]);
        else break;
    }
    unq(hull);
    return hull;
}

class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        vector<PT>v;
        for(auto it : trees){
            v.push_back(PT(it[0], it[1]));
        }
        auto ans = GrahamScan(v);
        vector<vector<int>>res;
        for(auto it : ans){
            vector<int>tt = {it.x, it.y};
            res.push_back(tt);
        }
        return res;
    }
};