ConvexHull

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

struct pp{
    int x,y,dis;
    double angle;
    pp(){}
    pp(int a,int b){
        x=a; y=b;
    }
    bool operator()(pp i, pp j){
        return i.y < j.y;
    }
    bool operator<(const pp &q)const{
        return angle < q.angle || (angle==q.angle && dis < q.dis);
    }
};
struct ConvexHull{
private:
    vector<pp> v, ret;
    int n;
    int ccw(pp a,pp b,pp c){
        int t = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
        if (t>0) return 1;
        else if (t<0) return -1;
        else return 0;
    }
    void calc(){
        sort(v.begin(),v.end(),pp());
        v[0].angle = -10000;
        int i;
        for (i=1;i<n;i++){
            v[i].angle = atan2(v[i].y-v[0].y,v[i].x-v[0].x);
            v[i].dis = (v[i].y-v[0].y)*(v[i].y-v[0].y) + (v[i].x-v[0].x)*(v[i].x-v[0].x);
        }
        sort(v.begin(),v.end());
        ret.push_back(v[0]);
        ret.push_back(v[1]);
        for (i=2;i<n;i++){
            while(ret.size()>1){
                int t = ccw(ret[ret.size()-1],ret[ret.size()-2],v[i]);
                if (t<=0) ret.pop_back();
                else break;
            }
            ret.push_back(v[i]);
        }
    }
public:
    ConvexHull(){};
    ConvexHull(vector<pp> _input) {
        v.clear(); ret.clear();
        v = _input;
        n = (int)v.size();
        calc();
    }
    vector<pp> result() {
        return ret;
    }
};