Convex Hull

/* Author : Bidhan Roy
 * Complexity : O (Nlog(N))
 * Handles Collinear points and duplicate points
 * Report at `mail2bidhan@gmail.com` if you find any buf
 */


point p0;
bool comp(point a,point b){
    i64 d=area(p0,a,b);
    if(d<0) return false;
    if(d) return true;
    return sqDist(p0,a)<sqDist(p0,b);
}
void convex(vector<point> &points,vector<point> &ans){
    int pos=0;
    rep(i,sz(points))
    if(points[pos].y>points[i].y || (points[pos].y==points[i].y && points[pos].x>points[i].x)) pos=i;
    p0=points[pos];
    sort(all(points),comp);
    int i=0;
    while(p0==points[i]) {
        i++;
        if(i==sz(points)) return ;
    }
    int start=i;
    ans.pb(points[i-1]);
    while(!area(ans[0],points[start],points[i])) {
        i++;
        if(i==sz(points)) return ;
    }
    i--;
    int sec=i;
    ans.pb(points[i]); bool one=1;
    while(!area(ans[0],ans[1],points[i])){
        i++;
        if(i==sz(points)) { if(one) return ; else break; }
        one=0;
    }
    if(i-1>sec) i--;
    if(i==sz(points)) return ;
    ans.pb(points[i]);
    i++;
    for(; i<sz(points); i++){
        while(area(ans[sz(ans)-2],ans[sz(ans)-1],points[i])<=0) ans.erase(ans.begin()+sz(ans)-1);
        ans.pb(points[i]);
    }
}


Go Back

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s